Homework 3 Dynamic Memory Allocator
Due Date: Friday 3/28/2025 @ 11:59pm
We HIGHLY suggest that you read this entire document, the book chapter, and examine the base code prior to beginning. If you do not read the entire document before beginning, you may find yourself doing extra work.
Start early so that you have an adequate amount of time to test your program!
The functions malloc, free, realloc, memalign, calloc, 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.
NOTE: In this document, we refer to a word as 2 bytes (16 bits) and a memory row as 4 words (64 bits). We consider a page of memory to be 4096 bytes (4 KB)
Introduction
You must read Chapter 9.9 Dynamic Memory Allocation Page 839 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 design strategies and implementation details of an allocator, this document will not cover this information. Instead, it will refer you to the necessary sections and pages in the textbook.
Takeaways
After completing this assignment, you will have a better understanding of:
● The inner workings of a dynamic memory allocator
● Memory padding and alignment
● Structs and linked lists in C
● errno numbers in C
● Unit testing in C
Overview
You will create an allocator for the x86-64 architecture with the following features:
● Free lists segregated by size class, using first-fit policy within each size class, augmented with a set of "quick lists" holding small blocks segregated by size.
● Immediate coalescing of large blocks on free with adjacent free blocks; delayed coalescing on free of small blocks.
● Boundary tags to support efficient coalescing.
● Block splitting without creating splinters.
● Allocated blocks aligned to "double memory row" (16-byte) boundaries.
● Free lists maintained using last in first out (LIFO) discipline.
● Use of a prologue and epilogue to avoid edge cases at the beginning and end of the heap.
● Obfuscation of block headers and footers to detect heap corruption and attempts to free blocks not previously obtained via allocation.
You will implement your own versions of the malloc, realloc, and free functions. You will also implement functions to calculate internal fragmentation and heap utilization.
You will use existing Criterion unit tests and write your own to help debug your implementation.
Free List Management Policy
Your allocator MUST use the following scheme to manage free blocks: Free blocks will be stored in a fixed array of NUM_FREE_LISTS free lists, segregated by size class (see Chapter 9.9.14 Page 863 for a discussion of segregated free lists). Each individual free list will be organized as a circular, doubly linked list (more information below). The size classes are based on a power-of-two geometric sequence (1, 2, 4, 8, 16, ...), according to the following scheme: The first free list (at index 0) holds blocks of the minimum size M (where M = 32 for this assignment). The second list (at index 1) holds blocks of size (M, 2M]. The third list (at index 2) holds blocks of size (2M, 4M]. The fourth list holds blocks whose size is in the interval (4M, 8M]. The fifth list holds blocks whose size is in the interval (8M, 16M], and so on. This pattern continues up to the interval (512M, 1024M], and then the last list (at index NUM_FREE_LISTS-1; i.e. 11) holds blocks of size greater than 1024M. Allocation requests will be satisfied by searching the free lists in increasing order of size class.
Quick Lists
Besides the main free lists, you are also to use additional "quick lists" as a temporary repository for recently freed small blocks. There are a fixed number of quick lists, which are organized as singly linked lists accessed in LIFO fashion. Each quick lists holds small blocks of one particular size. The first quick list holds blocks of the minimum size (32 bytes). The second quick list holds blocks of the minimum size plus the alignment size (32+16 = 48 bytes). This third quick list holds blocks of size 32+16+16 = 64 bytes, and so on. When a small block is freed, it is inserted at the front of the corresponding quick list, where it can quickly be found to satisfy a subsequent request for a block of that same size. The capacity of each quick list is limited; if insertion of a block would exceed the capacity of the quick list, then the list is "flushed" and the existing blocks in the quick list are removed from the quick list and added to the main free list, after coalescing, if possible.
Block Placement Policy
When allocating memory, use a segregated fits policy, modified by the use of quick lists as follows. When an allocation request is received, the quick list containing blocks of the appropriate size is first checked to try to quickly obtain a block of exactly the right size. If there is no quick list of that size (quick lists are only maintained for a fixed set of the smallest block sizes), or if there is a quick list but it is empty, then the request will be satisfied from the main free lists.
Satisfying a request from the main free lists is accomplished as follows: First, the smallest size class that is sufficiently large to satisfy the request is determined. The free lists are then searched, starting from the list for the determined size class and continuing in increasing order of size, until a nonempty list is found. The request is then satisfied by the first block in that list that is sufficiently large; i.e. a first-fit policy (discussed in Chapter 9.9.7 Page 849) is applied within each individual free list.
If there is no exact match for an allocation request in the quick lists, and there is no block in the main free lists that is large enough to satisfy the allocation request, sf_mem_grow should be called to extend the heap by an additional page of memory. After coalescing this page with any free block that immediately precedes it, you should attempt to use the resulting block of memory to satisfy the allocation request; splitting it if it is too large and no "splinter" (i.e. a remainder smaller than the minimum block size) would result. If the block of memory is still not large enough, another call to sf_mem_grow should be made; continuing to grow the heap until either a large enough block is obtained or the return value from sf_mem_grow indicates that there is no more memory.
As discussed in the book, segregated free lists allow the allocator to approximate a best-fit policy, with lower overhead than would be the case if an exact best-fit policy were implemented. The rationale for the use of quick lists is that when a small block are freed, it is likely that there will soon be another allocation request for a block of that same size. By putting the block in a quick list, it can be re-used for such a request without the overhead of coalescing and/or splitting that would be required if the block were inserted back into the main pool.
Splitting Blocks & Splinters
Your allocator must split blocks at allocation time to reduce the amount of internal fragmentation. Details about this feature can be found in Chapter 9.9.8 Page 849. Due to alignment and overhead constraints, there will be a minimum useful block size that the allocator can support. For this assignment, pointers returned by the allocator in response to allocation requests are required to be aligned to 16-byte boundaries; i.e. the pointers returned will be addresses that are multiples of 2^4. The 16-byte alignment requirement implies that the minimum block size for your allocator will be 32 bytes. No "splinters" of smaller size than this are ever to be created. If splitting a block to be allocated would result in a splinter, then the block should not be split; rather, the block should be used as-is to satisfy the allocation request (i.e., you will "over-allocate" by issuing a block slightly larger than that required).
How do the alignment and overhead requirements constrain the minimum block size? As you read more details about the format of a block header, block footer, and alignment requirements, you should try to answer this question.
Freeing a Block
When a block is freed, if it is a small block it is inserted at the front of the quick list of the appropriate size. Blocks in the quick lists are free, but the allocation bit remains set in the header to prevent them from being coalesced with adjacent blocks. In addition, there is a separate "in quick list" bit in the block header that is set for blocks in the quick lists, to allow them to be readily distinguished from blocks that are actually allocated. To avoid arbitrary growth of the quick lists, the capacity of each is limited to QUICK_LIST_MAX blocks. If an attempt is made to insert a block into a quick list that is already at capacity, the quick list is flushed by removing each of the blocks it currently contains and adding them back into the main free lists, coalescing them with any adjacent free blocks as described below. After flushing the quick list, the block currently being freed is inserted into the now-empty list, leaving just one block in that list. When a block is freed and added into the main free lists, an attempt should first be made to coalesce the block with any free block that immediately precedes or follows it in the heap. (See Chapter 9.9.10 Page 850 for a discussion of the coalescing procedure.) Once the block has been coalesced, it should be inserted at the front of the free list for the appropriate size class (based on the size after coalescing). The reason for performing coalescing is to combat the external fragmentation that would otherwise result due to the splitting of blocks upon allocation. Note that blocks inserted into quick lists are not immediately coalesced; they are only coalesced at such later time as the quick list is flushed and the blocks are moved into the main free lists. This is an example of a "deferred coalescing" strategy.
Block Headers & Footers
In Chapter 9.9.6 Page 847 Figure 9.35, a block header is defined as 2 words (32 bits) to hold the block size and allocated bit. In this assignment, the header will be 4 words (i.e. 64 bits or 1 memory row). The header fields will be similar to those in the textbook but you will maintain an extra bit for recording whether or not the block is currently in a quick list. Each free block will also have a footer, which occupies the last memory row of the block. The footer of a free block contains exactly the same information as the header.
Block Header Format:
+-------------------------------------+----------------------+--------+---
------+---------+ <- header
| payload size | block_size | unused
|in qklst | alloc |
| |(4 LSB's implicitly 0)| (0)
| (0/1) | (0/1) |
| (32 bits) | (28 bits) | 2 bits
| 1 bit | 1 bit |
+-------------------------------------+----------------------+--------+---
------+---------+ <- (aligned)
● The block_size field gives the number of bytes for the entire block (including header/footer, payload, and padding). It occupies the low-order 32 bits of the block header or footer, except that the four least-significant bits, which would normally always be zero due to alignment requirements, are used to store the allocation status (free/allocated) of that block and whether the block is currently in a quick list. This means that the four least-significant bits have to be masked when retrieving the block size from the header and when the block size is stored in the header the previously existing values of these bits have to be preserved.
● The alloc bit (bit 0, mask 0x1) is a boolean. It is 1 if the block is allocated and 0 if it is free.
● The in_qklst (bit 1, mask 0x2) is also a boolean. It is 1 if the block is currently in a quick list, and 0 if it is not. Note that if this bit is a 1, then the alloc bit will also be a 1.
● The high-order 32 bits of the block header will be used to store, for an allocated block, the payload size that was requested in the call to malloc or realloc that resulted in the allocation of that block. This information would not normally be stored by a real allocator, but we are doing it here to make it possible to track the utilization and internal fragmentation of the heap. For blocks that are free or in a quick list, this part of the header is ignored.
Here is an example of determining the block size required to satisfy a particular requested payload size. Suppose the requested size is 25 bytes. An additional 8 bytes will be required to store the block header, which must always be present. This means that a block of at least 33 bytes must be used, however due to alignment requirements this has to be rounded up to the next multiple of the alignment size. If the alignment size were 16 bytes (which would be just large enough to enable the memory returned by the allocator to store in an aligned fashion any of the basic data types supported by the x86-64 architecture), then a block of at least 48 bytes would have to be used. As a result, there would be 15 bytes of "padding" at the end of the payload area, which contributes to internal fragmentation. Besides the header, it is also necessary to store a footer, as well and next and previous links for the freelist. These will take an additional 24 bytes of space. But the payload area is 40 bytes (25 bytes plus 15 bytes of padding), which is certainly bigger than 24 bytes, so a block of total size 48 would be fine. Note that a block cannot be smaller than 32 bytes, as there there would not then be enough space to store the header, footer, and freelist links when the block is free.
Obfuscation of Headers and Footers
Your allocator has to satisfy one further requirement as regards the storage of the block headers and footers. The headers and footers will not be stored directly in memory; rather their contents will first be obfuscated by performing a bitwise XOR (C operator ^) with a "magic" value that is obtained by referencing the preprocessor symbol MAGIC. This value is set randomly (by the utility code provided for you) when the heap is first initialized. When a header or footer is read from memory, it must again be XOR'ed with the magic value to expose the true contents. The purpose of obfuscating the headers and footers in this way is to help detect attempts to free pointers that were not obtained from a previous call to malloc, and also to make it possible to detect some situations in which the heap has been corrupted by overwriting of headers and/or footers.
In the initial stages of debugging, you might find it helpful to turn off the header and footer obfuscation. This can be accomplished by making an initial call of sf_set_magic(0x0). The effect of this is that the magic value will then always be 0x0, rather than a randomly chosen value. Once you have your code working with obfuscation turned off in this way, don't forget to turn it back on again to test your code in the correct configuration, because the sf_set_magic() function will be replaced by a dummy version during grading.
Getting Started
Fetch and merge the base code for hw3 as described in hw0 from the following link:
https://gitlab02.cs.stonybrook.edu/cse320/hw3
Remember to use the --strategy-option=theirs flag with the git merge command as described in the hw1 doc to avoid merge conflicts in the Gitlab CI file.
Directory Structure
.
├── .gitignore
├── .gitlab-ci.yml
└── hw3
├── hw3.sublime-project
├── include
│ ├── debug.h
│ └── sfmm.h
├── lib
│ └── sfutil.o
├── Makefile
├── src
│ ├── main.c
│ └── sfmm.c
└── tests
└── sfmm_tests.c
The lib folder contains the object file for the sfutil 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.
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, including lib/sfutil.o, to make executables that are stored to the bin directory.
Note: make clean will not delete sfutil.o or the lib folder, but it will delete all other contained .o files.
The sfmm.h header file contains function prototypes and defines the format of the various data structures that you are to use.
DO NOT modify sfmm.h or the Makefile. Both will be replaced when we run tests for grading. If you wish to add things to a header file, please create a new header file in the include folder All functions for your allocator (sf_malloc, sf_realloc, sf_free, sf_fragmentation, and sf_utilization) must be implemented in src/sfmm.c.
The program in src/main.c contains a basic example of using the allocation functions. Running make will create a sfmm executable in the bin directory. This can be run using the command bin/sfmm.
Any functions other than sf_malloc, sf_free, sf_realloc WILL NOT be graded.