ICS 53 Principles in System Design Homework 4: Dynamic Memory Allocator
Introduction
For this assignment, you will write a dynamic memory allocator as an alternative to the
built-in version provided by glibc.
In addition to the lecture notes, you must read Chapter 9.9 Dynamic Memory Allocation before starting this assignment. This chapter contains all the theoretical information needed to complete this assignment. Since the textbook has sufficient information about the different allocator design strategies and implementation details, this document refers you to the necessary sections and pages of the textbook rather than repeating the information.
Takeaways
After completing this assignment you will have experience with and a better understanding
of:
- The inner workings of a dynamic memory allocator
- Memory Padding and Alignment
- Additional Experience with structs and pointers (Linked Lists) in C
- errno numbers in C
Remember to use the man pages!
Restrictions & Important Information
In this assignment,
- the use of functions malloc, free, realloc, memalign, calloc, mmap, etc. are NOT ALLOWED
in your implementation. If any of these functions, or any other function with similar
functionality is found in your program, you will receive a ZERO.
- Any main program(s) provided or created WILL NOT be graded. Your Makefile will also be
replaced for grading. Any changes to either of these files will not be graded. Any helper
functions should be placed in the helpers files!
- DO NOT modify the icsmm.h header file. We will replace this file when we perform tests for
grading.
The Allocator
The assignment goal is to create an explicit free list allocator with best-fit placement,
LIFO-ordered (insert-at-head), with forward (header) coalescing only, and block splitting
without creating splinters. Specifically, implement a version of the malloc, and free functions.
Explicit Free List Management Policy
You MUST use an explicit freelist, as described in Chapter 9.9.13 Page 862, to manage free
blocks.
Your allocator will manage your freelist by inserting newly freed blocks in the list via
LIFO-order (insert at head). The head of the list will always refer to the most recently free'd
block within the managed heap space.
Block Placement Policy
Your allocator will support the best-fit placement policy, as described in Chapter 9.9.7 Page
849. The free list is searched to locate the smallest block that satisfies the malloc request. If
the exact block size required to satisfy the request is found, the search is terminated early
and the block is used.
Immediate Coalescing
Your implementation performs immediate forward (header) coalescing upon free() as
described in Chapter 9.9.10 Page 850.
The main assignment only performs coalescing with blocks adjacent to the header in the
heap (eg. lower addressed blocks). Coalescing with blocks adjacent to the footer (Case 3)
and in both directions (Case 4) is extra credit and will be discussed at the end of the
document. NOTE: You must create 2 separate implementations if you choose to do the extra
credit.
Side Note: The case numbers mentioned in the provided videos may differ from the figure below. However, the explanation is correct - coalesce with the block lower addressed block in the heap for the regular assignment.
---
Each block uses boundary tags as described in Chapter 9.9.11 Page 851. In Chapter 9.9.11 Page 852 Figure 9.39, the boundary tag (footer) is defined as a single 32-bit double word with the block size and allocated bit. Your boundary tag must be a single memory row of 64-bits in a similar format.
Splitting Blocks & Splinters
If possible, the allocator upon malloc/realloc allocation must split off the usable excess space
into a new free block. It may be possible to split the block into two blocks (one for the
requested allocation, and one new smaller free block) if the selected free block is larger than
the requested allocation. This will help reduce the amount of internal fragmentation. Details
about this feature can be found in Chapter 9.9.8 Page 849.
When splitting blocks your allocator MUST NOT create splinters. Splinters are small (< 32
bytes, in this case) groups of free bytes left after inserting a relatively large payload into free
space. To avoid this your allocator must “over” allocate the amount of memory requested by
the malloc call so that these small useless blocks are not inserted into the free list, but
remain with the allocated block.
Blocks
In Chapter 9.9.6 Page 847 Figure 9.35, the block header is defined as a single 32-bit value
with block size and the allocated bit. In this assignment, the header is defined as a single
64-bit value, with a layout similar to the header in the textbook.
We will define the term Memory Row to represent 64-bits in size.
---
Block Header Format:
+-----------------+--------------------+-------------------+
| padding_amount | hid | block_size |
| (in bytes) | (0xAABBCCDDEEF) | (in bytes) |
| 4 bits | 44 bits | 16 bits |
+-----------------+--------------------+-------------------+
Block Header Format - identifying the position of the allocated bit:
+-----------------+--------------------+-------------------+---+
| padding_amount | hid | block_size | a |
| (in bytes) | (0xAABBCCDDEEF) | | |
| 4 bits | 44 bits | 15 bits | 1 | +-----------------+--------------------+-------------------+---+
Block Footer Format:
+--------------------+-------------------+
| fid | block_size |
| (0xBEEFC AFE BEEF) | (in bytes) |
| 48 bits | 16 bits |
+--------------------+-------------------+
Block Footer Format - identifying the position of the allocated bit:
+--------------------+-------------------+---+
| fid | block_size | a |
| (0xBEEFC AFE BEEF) | | |
| 48 bits | 15 bits | 1 | +--------------------+-------------------+---+
• The maximum size of memory which can be managed by this allocator is 2^16. Therefore the block_size can never exceed this value. The block_size field represents the total number of bytes for the entire block (header, payload, padding - when needed, footer). The least-significant bit of the block_size field is used as the allocated bit (as explained in the textbook).
NOTE: We have limited the amount of managed space for this assignment by setting a maximum number of heap pages. As a result, your implementation and the testcases will not test block up to 2^16
• Within the block_size field of the header and footer the least significant bit is used as a flag.
The least significant bit, position 2^0 labeled a, denotes if the block is allocated (1) or not (0).
The bit must be extracted from the block_size field to obtain the true block size in bytes.
• The padding_amount field represents the amount of payload padding required in the block
for alignment purposes ONLY. This field value DOES NOT include padding bytes added to
the block due to eliminating splinter blocks. [5/14 6:59pm Added to be clear. EdD #723]
• The hid and fid fields are bits/values used by your allocator to identify a valid header/footer. The hid field MUST BE SET in the header to 0x3AABBCCDDEEF and the fid MUST BE SET to 0x2BEEFC AFE BEEF in the footer. Macro constants for these values are defined in the header file for you to use.
Block Constraints
Each free and allocated block in the allocator must adhere to certain constraints. To
understand these constraints, we must first consider the sizes of primitive data types in your
course environment.
|
C declaration |
Intel data type |
GAS suffix |
x86-64 Size (Bytes) |
|
char |
Byte |
b |
1 |
|
short |
Word |
w |
2 |
|
int |
Double word |
1 |
4 |
|
unsigned |
Double word |
1 |
4 |
|
long int |
Quad word |
q |
8 |
|
unsigned long |
Quad word |
q |
8 |
|
pointer |
Quad word |
q |
8 |
|
float |
Single precision |
s |
4 |
|
double |
Double precision |
d |
8 |
|
long double |
Extended precision |
t |
16 |
As the largest primitive data type in the system is 16 bytes in size, the payload of each block must be 16-byte aligned. Why? Since the allocator does not know what data you plan to store in the dynamically allocated space, it must ensure that the caller can store any primitive data type without an alignment error.
As such, the following constraints apply to all free and allocated blocks created by the
allocator:
• Each block begins with the header (8 bytes), which must have an address that is 8-byte
aligned, but not 16-byte aligned.
• The minimum payload size is 16 bytes (for next and prev pointers for explicit list).
• Each block ends with a boundary tag (8 bytes), aka footer, which must have an address
that is 16-byte aligned.
Therefore, the minimum block size is 32 bytes (header + payload + footer). The block size
will always be a multiple of 16 bytes due to alignment.
Getting Started
Download the base code for this assignment: hw4_docker.tar or hw4_UTM.tar. [5/16 6:42pm
Docker tar updated to correct issue with icsutil.o. Specifically, ics_inc_brk() failed after 16
calls, not 5. Corrected file]
The basecode contains the following file structure.
hw4/
├── include/
│ ├── debug.h
│ ├── helpers.h
│ └── icsmm.h
├── lib/
│ └── icsutil.o
├── Makefile
├── src/
│ ├── helpers.c
│ └── icsmm.c
└── tests/ // Your testing files. These will be ignored during grading
├── makefile // This makefile is called by Makefile in hw4/
└── test1.c
The provided Makefile creates object files from the .c files in the src directory, places the object files inside the build directory, and then links the object files together with EACH of the test files in the tests directory to create executables, located in the bin directory. The two targets of the makefile are all and clean.
The provided makefile is SUPER strict. It uses the gcc flags -Wall and -Werror. The flag -Wall will alert you to any errors the compiler may detect during the compilation process. The flag -Werror will turn all the warnings into errors. This will prevent the compiler from successfully finishing the compilation process and creating a binary if any warnings or errors exist. More information on these flags is in the extended debugging document in the Resources section of Module I. We added these flags to help you identify errors that can occur due to casting errors.
Inside this structure is a build folder in the hw4 directory. The lib folder contains the object file for the icsutil library. This library provides you with several functions to aid you with the implementation of your allocator. Do NOT delete this file as it is an essential part of your homework assignment. Note: make clean will not delete icsutil.o in the lib folder.
All functions for your allocator (ics_malloc and ics_free) must be implemented in src/icsmm.c. There is a small sample main file (tests/test1.c) to test your allocator. After your
allocator passes these very basic tests, you should create your own tests (in this file or in a new .c file in the tests folder - the makefile will compile each of your tests/*.c files separately) as well as the tests provided on Gradescope.
Remember! Any main program(s) provided or which you create in the tests folder WILL NOT
be graded. Your Makefile will also be replaced for grading. Any changes to either of these
files will not be graded. Any helper functions should be placed in the existing files!
DO NOT modify the icsmm.h header file. We will replace this file when we perform tests for
grading. If you wish to add things to a header file, please create a new header file in the
include folder.
Initialization Library
A hw4/lib/icsutil.o object file is provided in the build directory. When linked with your program, this object file allows you to use the icsutil library.
As these functions are provided to you in a pre-built .o file, the source is not available. Debugging of these functions with gdb is not possible. You must treat them as black boxes.
This library contains the following functions:
The function ics_mem_init MUST be used to initialize and request memory from the heap in the user program. The allocator must use ics_inc_brk to request space on the heap. Existing C library functions will not work.
-
Your implementation will manage a maximum of 5 pages of memory (1 page = 4096 bytes). Any requests that exceed this are considered an ERROR (return NULL).
A real allocator may use the brk/sbrk syscalls for small memory allocations and mmap/munmap syscalls for large allocations. To allow your program to use other functions provided by glibc, that rely on glibc's allocator, we provided a safe wrapper around sbrk. This makes it so that the heap breakpoint is not altered by glibc's allocator and accidentally can destroy the memory managed by your allocator.
Refer to the sample main program provided (hw4/tests/test1.c) for an example of how these provided library functions are used.
Allocation Functions
Implement the following three functions in src/icsmm.c. The file include/icsmm.h contains the function prototypes. All documentation about these functions is found here.
Read the manpage on errno and this description to review its purpose and usage.
Make sure these functions have these exact names and argument types. They must also appear in the icsmm.c. If you do not name the functions correctly with the correct argument types, your program will not compile or run on Gradescope.
The allocator will start with no space allocated on the heap. When the user program makes the first call to ics_malloc, the allocator must request space to manage using ics_inc_brk(). The allocator then initializes the returned space into a large free block for the allocator to manage. A prologue and epilogue will be needed to ensure proper alignment!
-
Note: We are not using the special prologue block which is mentioned in the textbook for the invariant form on page 855-856 and Figure 9.42. Your prologue (and epilogue, for that matter) should only be 8 bytes (with size of 0 and allocated bit set).
The prologue is set as an ics_footer with block size of 0 and the allocated bit set. The epilogue is set as an ics_header with padding_amount and block_size of 0 and allocated bit set. More information on these structures in the next section.
Once the allocator has memory space to manage, then the first and all subsequent calls to ics_malloc can be handled identically. ics_malloc selects the appropriate block in the free list according to the block placement policy (best-fit starting from the front of the list). If the selected block is larger than required and would not produce a splinter block when split, then the block should be split according to the split policy. Set the headers and footers for the selected block and (if necessary) the split block. Place the newly created split block in the free list at the head of the list. Return the address of the payload in the selected allocated block.
If the entire free list is traversed and a free block was not selected, more memory space must be requested from ics_inc_brk.
- If no additional heap space is available, return NULL and ENOMEM as prior specified. Remember, a maximum of 5 pages of memory can be requested from ics_inc_brk.
- If additional heap space is returned by ics_inc_brk, coalesce this new memory space with the free block at the end of the previously managed heap space (if applicable) or create a new block and place it in the free list according to the block placement policy (LIFO). Now again try to satisfy the malloc request. (Note this step should be repeated until ics_inc_brk fails.)
(i) the ptr is in the managed heap space,
(ii) check the hid field of the ptr's header,
(iii) check the fid field of the ptr's footer,
(iv) check that the block_size in the ptr's header and footer are equal, and
(v) the allocated bit is set in both ptr's header and footer.
int ics_free(void *ptr); ```
When implementing your ics_free function, consider the case where an invalid pointer is passed to the function. Before freeing this pointer, your ics_free function should check if the pointer being freed belongs to an allocated block.
How? This is not 100% foolproof, but you can do your best to try and ensure this by
performing checks on what should be in the header and footer of the block. At a minimum,
check the following:
- ptr is in between the prologue and epilogue
- The allocated bit a is set in both the blocks's header and footer
- Check the hid field of the block's header (defined in icsmm.h)
- Check the fid field of the block's footer (defined in icsmm.h)
- Check that the block_size in the block's header and footer are equal
If this pointer does belong to an allocated block, the block is to be inserted into the free list. In this case, coalescing may be required. Use the header of the block being free'd to check the footer of the adjacent block (lower addressed in memory only). If the block is free, remove it from the linked list, coalesce it with the block being free'd and insert the newly formed block into the free list in LIFO-order. When successful (with or without coalescing), ics_free returns 0. Otherwise, ics_free returns -1 and sets errno to EINVAL.
The padding_size field is not used when a block is unallocated and does not need to be reset. Leave its value unchanged when freeing. It will be overwritten on the next allocation of the block.
Implementation Details
To assist you with your implementation and to enable grading of the assignment, we have provided the following constructs in the provided base code. In addition, we have provided functions to help visualize each block and the state of your free list.
Freelist head
In the file src/icsmm.c there is a pointer declared freelist_head, which is made available
globally by the extern keyword in icsmm.h. This pointer MUST be used by your allocator to
reference the head of your free list.
/*
* The allocator MUST store the head of its free list in this variable.
* Doing so will make it accessible via the extern keyword.
* This will allow ics_freelist_print to access the value from a different file.
*/
extern ics_free_header* freelist_head;
```
You MUST use this pointer to access the head of your explicit freelist. We will use this pointer to grade your assignment!
Block Headers & Footer
We have repeatedly studied and utilized structures for the casting of memory space this term. All that work was to prepare for this assignment!
The block header and footer formats and field sizes are specified in include/icsmm.h. A block header struct is defined for you as:
#define PADDING_SIZE_BITS 4 #define HID_SIZE_BITS 44 #define BLOCK_SIZE_BITS 16 #define FID_SIZE_BITS 48
#define HID 0xAABBCCDDEEFUL #define FID 0xBEEFC AFE BEEFUL
struct ics_free_header *prev;
} ics_free_header;
```
Lastly, a struct for the boundary tag (footer) is also included and defined as:
typedef struct __attribute__((__packed__)) ics_footer {
uint64_t block_size : BLOCK_SIZE_BITS;
uint64_t fid : FID_SIZE_BITS;
} ics_footer; ```
Using your experience from the struct casting labs, you can cast blocks of memory with these structs in order to easily access the different fields of information of your memory allocator blocks.
An allocated block cast with ics_header would be visualized as:
+-----------------+--------------------+-------------------+
| padding_amount | hid | block_size
| (in bytes) | (0xAABBCCDDEEF) | (in bytes)
| 4 bits | 44 bits | 16 bits |
+-----------------+--------------------+-------------------+
```
|<- Header Block |
A free block cast with ics_free_header would be visualized as:
+-----------------+--------------------+-------------------+
| padding_amount | hid | block_size
| (in bytes) | (0xAABBCCDDEEF) | (in bytes)
| 4 bits | 44 bits | 16 bits |
+-----------------+--------------------+-------------------+
| next: %p |
+-----------------+--------------------+-------------------+
| prev: %p |
+-----------------+--------------------+-------------------+
```
Helper Block Print functions
|<- Header Block |
In the file hw4/lib/icsutil.o, the functions ics_freelist_print, ics_header_print, and ics_payload_print are provided to help you visualize your freelist and allocated blocks.
The function ics_header_print takes the address of a memory block header and prints to STDERR a visual representation of your memory blocks. The function ics_payload_print takes the address of the payload of a memory block (the address that is returned by ics_malloc) and prints to STDERR the same visual representation of the memory block. Below we display the format printed by ics_header_print and ics_payload_print.
/*
-
* Function which prints human-readable block format to STDERR *
-
* @param block Address of the block header in memory. *
-
* @return -1 on failure, 0 on success. Failure is most likely due to accessing
-
* invalid an address outside of the allocators' current heap space. */
int ics_header_print(void* block);
/*
-
* Prints human-readable block format from the address of the payload to STDERR.
-
* IE. subtracts header size from the data pointer to obtain the address
-
* of the block header. Calls ics_blockprint internally to print. *
-
* @param data Pointer to payload data in memory (value returned by ics_malloc). *
-
* @return -1 on failure, 0 on success. Failure is most likely due to accessing
-
* invalid an address outside of the allocators' current heap space. */
int ics_payload_print(void *data);
The ics_freelist_print function is designed to help debug/visualize the freelist. It starts by printing out the following information: which kind of freelist is being used (hard coded to Explicit), and the current state of the heap and heap pointers.
It then traverses the free list starting from freelist_head pointer and prints out the address of the free block and its block_size for the entire freeblock for each block in the list. If the freelist is "broken" (meaning it can not be properly traversed for any reason), the function will print an error message and stop printing.
/*
-
* Function that prints human-readable block format with information about
-
* the state of the freelist and each block in the freelist to STDERR. *
-
* Will print an error upon attempting to print */
void ics_freelist_print();
Things to Remember
- HUGE sized allocations: any request larger than 5 Pages (1 Page = 4096 bytes) should return NULL and set errno to ENOMEM.
- Make sure that the memory returned is aligned and padded correctly for your course environment.When writing your program try to comment as much as possible. Try to stay consistent with your formatting too! This will make it easier to debug your program!
Extra Credit (up to 10 points)
First, complete and submit the original assignment to Gradescope WITHOUT the extra credit implemented. The gradescope tests for the standard assignment are testing for operation under those set conditions ONLY.Upload your extra credit implementation to the separate Gradescope assignment. Note, the EC autograder provides no visible tests except compilation. You should extensively test your own implementation to ensure proper functionality.
(5 points) Add the remaining coalescing cases (see figure) to your existing implementation.
(5 points) Implement ics_realloc. Completion of the coalescing EC must be completed. Testing of ics_realloc assumes completed all coalescing cases are working.
/*
-
* Resizes the dynamically allocated memory, pointed to by ptr, to at least size
-
* bytes. All equal or larger allocations are placed in a new block selected from the
-
* free list (eg. the returned pointer value cannot be equal to ptr). Entire payload
-
* is copied into the newly allocated space which realloc returns.
-
* If size is a reduction in space, a new block is not selected. The current block is
-
* resized as necessary, creating a new free block if the free'd space will not produce
-
* a splinter. *
-
* @param ptr Address of the previously allocated memory region. *
-
* @param size The minimum size to resize the allocated memory to. *
-
* @return If successful, the pointer to the block of allocated memory is
-
* returned. Else, NULL is returned and errno is set appropriately. *
-
* If there is no memory available ics_malloc will set errno to ENOMEM. *
-
* If ics_realloc is called with an invalid pointer, set errno to EINVAL. *
-
* If ics_realloc is called with a valid pointer and a size of 0, the allocated
-
* block is free'd and return NULL. */
void* ics_realloc(void *ptr, size_t size);
Your allocator will ALWAYS select a new block from the free list for a larger reallocation (allocations that cannot fit in the current block). [5/17 9:23am Added to be clear EdD #728]
If the ics_realloc call requests a larger chunk of memory, a free block of the larger size must be located (extending managed space if needed). The payload is copied to the new block and the existing block freed. It is possible that no additional memory is available to satisfy this request and an error will occur (ENOMEM).
If the ics_realloc call requests a smaller chunk of memory, the same block will be used. If the amount of space requested to be freed does not form a splinter, the portion of the block is freed and placed in the allocator's free list. Data truncation may occur, and that’s ok - it is what the caller requested!
