3/15/2019 CSE 320 / hw3-doc · GitLab
Correct two typos.
Gene Stark authored 1 day ago
67579d83
Name Last update
README.md Correct two typos. 1 day ago
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)
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.
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
You will create an allocator for the x86-64 architecture with the following features:
Main free list using first-fit placement policy, 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 with footer optimization that allows footers to be omitted from allocated blocks.
Block splitting without creating splinters.
0 0 https://gitlab02.cs.stonybrook.edu/cse320/hw3-d
README.md
Homework 3 Dynamic Memory Allocator - CSE 320 - Spring 2019
Professor Eugene Stark
Due Date: Friday 3/29/2019 @ 11:59pm
Introduction
Takeaways
Overview
3/15/2019 CSE 320 / hw3-doc · GitLab
https://gitlab02.cs.stonybrook.edu/cse320/hw3-doc 2/12
Allocated blocks aligned to "double memory row" (16-byte) boundaries.
Free lists maintained using last in first out (LIFO) discipline.
You will implement your own versions of the malloc, realloc, and free functions.
You will use existing Criterion unit tests and write your own to help debug your implementation.
Your allocator MUST use the following scheme to manage free blocks: a "main" free list, augmented with a set of "quick lists" that hold small
blocks segregated by size (see Chapter 9.9.14 Page 863 for a discussion of segregated free lists). Both the main list and the quick lists will be
accessed using a last in first out (LIFO) discipline.
When allocating memory, use first-fit placement (discussed in Chapter 9.9.7 Page 849), 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 list.
If there is no exact match for an allocation request in the quick lists, and there is no block in the main free list 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 as usual
if it is too large and no splinter 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.
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. Note that the minimum useful block size is 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).
🤔 Why is the minimum block size 32? As you read more details about the format of a block header, block footer, and alignment
requirements, think about how these constrain the minimum block size.
When a block is freed, if the block is small enough for there to be a corresponding quick list, then the block will be placed at the front of that
quick list; otherwise the block will be inserted at the front of the main free list. Blocks added to quick lists are not coalesced, whereas each block
added to the main free list is subject to immediate coalescing with any free block immediately preceding or following it in the heap.
There is a fixed limit on the length of a quick list. If a block to be freed would increase the length of a quick list beyond the limit, then that quick
list is flushed by removing all the blocks currently in it and inserting them into the main free list (with coalescing). Then the block to be freed is
added to the now-empty quick list, leaving it as the only block in that list.
The idea of quick lists is to try to reduce the overhead involved with coalescing by avoiding immediate coalescing of small blocks for which
allocation requests are likely to be received in the near future. This tends to avoid repeated coalescing and splitting to satisfy small allocation
requests. In addition, by keeping the the small blocks segregated by size, some of the benefits of a best-fit placement policy can be achieved
without having to search through all the free blocks.
Your implementation must perform coalescing when inserting a block into the main free list. This essentially amounts to the procedure
described in Chapter 9.9.10 Page 850. The only time coalescing is performed is when a block is being added to the main free list (not a quick
list) as a result of a call to sf_free or sf_realloc , and just after sf_mem_grow has been called.
In Chapter 9.9.6 Page 847 Figure 9.35, the 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 keep an extra
field for recording whether or not the previous block is allocated (i.e. for the the optimization that permits footers to be omitted from allocated
blocks).
Block Header Format (allocated block):
+--------------------------------------------+------------------------+---------+---------+ <- header
| requested_size | block_size |prv alloc| alloc |
| | (2 LSB's implicitly 0) | (0/1) | (1) |
| 32 bits | 32 bits | 1 bit | 1 bit |
+--------------------------------------------+------------------------+---------+---------+ <- (aligned)
Free List Management Policy
Block Placement Policy
Splitting Blocks & Splinters
Freeing a Block
Immediate Coalescing
Block Headers & Footers
3/15/2019 CSE 320 / hw3-doc · GitLab
https://gitlab02.cs.stonybrook.edu/cse320/hw3-doc 3/12
+ + + + + < (aligned)
Block Header Format (free block):
+--------------------------------------------+------------------------+---------+---------+ <- header
| unused | block_size |prv alloc| alloc |
| | (2 LSB's implicitly 0) | (0/1) | (1) |
| 32 bits | 32 bits | 1 bit | 1 bit |
+--------------------------------------------+------------------------+---------+---------+ <- (aligned)
| |
| Pointer to next free block |
| |
+-----------------------------------------------------------------------------------------+
| |
| Pointer to previous free block |
| |
+-----------------------------------------------------------------------------------------+
Block Footer Format (free block only):
+--------------------------------------------+------------------------+---------+---------+ <- footer
| unused | block_size |prv alloc| alloc |
| | (2 LSB's implicitly 0) | (0/1) | (0) |
| 32 bits | 32 bits | 1 bit | 1 bit |
+--------------------------------------------+------------------------+---------+---------+
NOTE: Footer contents must always be identical to header contents, including "unused" fields.
The block_size field gives the number of bytes for the entire block (including header/footer, payload, and padding). It occupies the 32
least-significant bits of the block header or footer, except that the two least-significant bits of the block size, which would normally always
be zero due to alignment requirements, are used to store the allocation status (free/allocated) of that block and of the immediately
preceding block in the heap. This means that these two 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 two bits have to be preserved.
The requested_size field is 32 bits. It is the number of bytes that the client requested.
The alloc bit is a boolean. It is 1 if the block is allocated and 0 if it is free.
The prev_alloc bit is also a boolean. It is 1 if the immediately preceding block in the heap is allocated and 0 if it is not.
🤔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. That means 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 16, which is 48.
As a result, there will be 15 bytes of "padding" at the end of the payload area, which contributes to internal fragmentation. Besides the
header, when the block is freed, it will also be necessary to store a footer, as well and next and previous links for the freelist. These will
take an additional 24 bytes of space, however when the block is free there is no payload so the payload area can be used to store this
information, assuming that the payload area is big enough in the first place. 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 will be fine. Note that if a block is smaller than 32 bytes,
there would not be enough space to store the header, footer, and freelist links when the block is free. This is why the minimum block
size is 32 bytes.
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.
Fetch and merge the base code for hw3 as described in hw0 from the following link: https://gitlab02.cs.stonybrook.edu/cse320/hw3
.
├── .gitlab-ci.yml
└── hw3
├── include
│ ├── debug.h
│ └── sfmm.h
├── lib
│ └── sfutil.o
├── Makefile
├── src
│ ├── main.c
│ └── sfmm.c
Getting Started
Directory Structure
3/15/2019 CSE 320 / hw3-doc · GitLab
https://gitlab02.cs.stonybrook.edu/cse320/hw3-doc 4/12
└── 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 , and sf_free ) must be implemented in src/sfmm.c .
The program in src/main.c contains a basic example of using the initialization and allocation functions together. 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 , and sf_realloc WILL NOT be graded.
You will implement the following three functions in the file src/sfmm.c . The file include/sfmm.h contains the prototypes and documentation
found here.
Standard C library functions set errno when there is an error. To avoid conflicts with these functions, your allocation functions will set
sf_errno , a variable declared as extern in sfmm.h .
/*
* This is your implementation of sf_malloc. It acquires uninitialized memory that
* is aligned and padded properly for the underlying system.
*
* @param size The number of bytes requested to be allocated.
*
* @return If size is 0, then NULL is returned without setting sf_errno.
* If size is nonzero, then if the allocation is successful a pointer to a valid region of
* memory of the requested size is returned. If the allocation is not successful, then
* NULL is returned and sf_errno is set to ENOMEM.
*/
void *sf_malloc(size_t size);
/*
* Resizes the memory pointed to by ptr to size bytes.
*
* @param ptr Address of the memory region to resize.
* @param size The minimum size to resize the memory to.
*
* @return If successful, the pointer to a valid region of memory is
* returned, else NULL is returned and sf_errno is set appropriately.
*
* If sf_realloc is called with an invalid pointer sf_errno should be set to EINVAL.
* If there is no memory available sf_realloc should set sf_errno to ENOMEM.
*
* If sf_realloc is called with a valid pointer and a size of 0 it should free
* the allocated block and return NULL without setting sf_errno.
*/
void* sf_realloc(void *ptr, size_t size);
/*
* Marks a dynamically allocated region as no longer in use.
* Adds the newly freed block to the free list.
*
* @param ptr Address of memory returned by the function sf_malloc.
*
* If ptr is invalid, the function calls abort() to exit the program.
*/
void sf_free(void *ptr);
Allocation Functions
3/15/2019 CSE 320 / hw3-doc · GitLab
https://gitlab02.cs.stonybrook.edu/cse320/hw3-doc 5/12
😱 Make sure these functions have these exact names and arguments. They must also appear in the correct file. If you do not name
the functions correctly with the correct arguments, your program will not compile when we test it. YOU WILL GET A ZERO
In the build directory, we have provided you with the sfutil.o object file. When linked with your program, this object file allows you to
access the sfutil library, which contains the following functions:
This library contains the following functions:
/*
* Any program using the sfmm library must call this function ONCE
* before issuing any allocation requests. This function DOES NOT
* allocate any space to your allocator.
*/
void sf_mem_init();
/*
* Any program using the sfmm library must call this function ONCE
* after all allocation requests are complete. If implemented cleanly,
* your program should have no memory leaks in valgrind after this function
* is called.
*/
void sf_mem_fini();
/*
* This function increases the size of your heap by adding one page of
* memory to the end.
*
* @return On success, this function returns a pointer to the start of the
* additional page, which is the same as the value that would have been returned
* by sf_mem_end() before the size increase. On error, NULL is returned
* and sf_errno is set to ENOMEM.
*/
void *sf_mem_grow();
/* The size of a page of memory returned by sf_mem_grow(). */
#define PAGE_SZ 4096
/*
* @return The starting address of the heap for your allocator.
*/
void *sf_mem_start();
/*
* @return The ending address of the heap for your allocator.
*/
void *sf_mem_end();
The function sf_mem_init MUST be used to initialize memory. It is to be called once BEFORE using any of the other functions from sfutil.o .
The function sf_mem_grow is to be invoked by sf_malloc , at the time of the first allocation request to set up the heap prologue and epilogue
and obtain an initial free block, and on subsequent allocations when a large enough block to satisfy the request is not found.
😱 As these functions are provided in a pre-built .o file, the source is not available to you. You will not be able to debug these using
gdb. You must treat them as black boxes.
For this assignment, your implementation MUST ONLY use sf_mem_grow to extend the heap. DO NOT use any system calls such as brk or sbrk
to do this.
Function sf_mem_grow returns memory to your allocator in pages. Each page is 4096 bytes (4 KB) and there are a limited, small number of pages
available (the actual number may vary, so do not hard-code any particular limit into your program). Each call to sf_mem_grow extends the heap
by one page and returns a pointer to the new page (this will be the same pointer as would have been obtained from sf_mem_end before the call
to sf_mem_grow .
The sf_mem_grow function also keeps track of the starting and ending addresses of the heap for you. You can get these addresses through the
sf_mem_start and sf_mem_end functions.
Initialization Functions
sf_mem_grow
3/15/2019 CSE 320 / hw3-doc · GitLab
https://gitlab02.cs.stonybrook.edu/cse320/hw3-doc 6/12
😄 A real allocator would typically use the brk/sbrk system calls calls for small memory allocations and the mmap/munmap system
calls for large allocations. To allow your program to use other functions provided by glibc, which rely on glibc's allocator (i.e. malloc ),
we have provided sf_mem_grow as a safe wrapper around sbrk. This makes it so your heap and the one managed by glibc do not
interfere with each other.
The table below lists the sizes of data types (following Intel standard terminlogy) on x86-64 Linux Mint:
C declaration Data type x86-64 Size (Bytes)
char Byte 1
short Word 2
int Double word 4
long int Quadword 8
unsigned long Quadword 8
pointer Quadword 8
float Single precision 4
double Double precision 8
long double Extended precision 16
🤓 You can find these sizes yourself using the sizeof operator. For example, printf("%lu\n", sizeof(int)) prints 4
In this assignment we will assume that each "memory row" is 8 bytes (64 bits) in size. All pointers returned by sf_malloc are to be "double
memory row" aligned; that is, they will be addresses that are multiples of 16. This will permit such pointers to be used to store values of the
largest data type ( long double ) supported by the hardware.
The various header and footer formats are specified in include/sfmm.h :
Format of an allocated memory block
+-----------------------------------------------------------------------------------------+
| 64-bits wide |
+-----------------------------------------------------------------------------------------+
+--------------------------------------------+------------------------+---------+---------+ <- header
| requested_size | block_size |prv alloc| alloc |
| | (2 LSB's implicitly 0) | (0/1) | (1) |
| 32 bits | 32 bits | 1 bit | 1 bit |
+--------------------------------------------+------------------------+---------+---------+ <- (aligned)
| |
| Payload and Padding |
| (N Memory Rows) |
| |
| |
+-----------------------------------------------------------------------------------------+
Format of a free memory block
+--------------------------------------------+------------------------+---------+---------+ <- header
| unused | block_size |prv alloc| alloc |
| | (2 LSB's implicitly 0) | (0/1) | (1) |
| 32 bits | 32 bits | 1 bit | 1 bit |
+--------------------------------------------+------------------------+---------+---------+ <- (aligned)
| |
| Pointer to next free block |
| |
+-----------------------------------------------------------------------------------------+
| |
Implementation Details
Memory Row Size
Block Header & Footer Fields
3/15/2019 CSE 320 / hw3-doc · GitLab
https://gitlab02.cs.stonybrook.edu/cse320/hw3-doc 7/12
| |
| Pointer to previous free block |
| |
+-----------------------------------------------------------------------------------------+
| |
| Unused |
| (N Memory Rows) |
| |
| |
+--------------------------------------------+------------------------+---------+---------+ <- footer
| unused | block_size |prv alloc| alloc |
| | (2 LSB's implicitly 0) | (0/1) | (0) |
| 32 bits | 32 bits | 1 bit | 1 bit |
+--------------------------------------------+------------------------+---------+---------+
NOTE: Footer contents must always be identical to header contents, including "unused" fields.
The sfmm.h header file contains C structure definitions corresponding to the above diagrams:
#define THIS_BLOCK_ALLOCATED 0x1
#define PREV_BLOCK_ALLOCATED 0x2
#define BLOCK_SIZE_MASK 0xfffffffc
/* Structure of a block header or footer. */
typedef struct sf_header {
unsigned block_size : 32;
unsigned requested_size : 32;
} sf_header;
/* Structure of a block. */
typedef struct sf_block {
sf_header header;
union {
/* A free block contains links to other blocks in a free list. */
struct {
struct sf_block *next;
struct sf_block *prev;
} links;
/* An allocated block contains a payload (aligned), starting here. */
char payload[0];
} body;
} sf_block;
For sf_block , the body field is a union , which has been used to emphasize the difference between the information contained in a free block
and that contained in an allocated block. If the block is free, then its body has a links field, which is a struct containing next and prev
pointers. If the block is allocated, then its body does not have a links field, but rather has a payload , which starts at the same address that
the links field would have started if the block were free. The size of the payload is obviously not zero, but as it is variable and only
determined at run time, the payload field has been declared to be an array of length 0 just to enable the use of bp->body.payload to obtain a
pointer to the payload area, if bp is a pointer to sf_block .
👍You can use casts to convert a generic pointer value to one of type sf_block or sf_header , in order to make use of the above
structure definitions to easily access the various fields.
In the file include/sfmm.h , you will see the following declaration:
struct sf_block sf_free_list_head;
The variable sf_free_list_head is the head of the main free list, which is maintained as a circular, doubly linked list. Each node in the list
contains a next pointer that points to the next node in the list, and a prev pointer that points the previous node. The variable
sf_free_list_head is a dummy, "sentinel" node, which is used to connect the beginning and the end of the list. This node is always present
and (aside from its next and free pointers) does not contain any other data. If the list is empty, then the fields
sf_freelist_head.body.links.next and sf_freelist_head.body.links.prev both contain &sf_freelist_head (i.e. the sentinel node points
back to itself). If the list is nonempty, then sf_freelist_head.body.links.next points to the first node in the list and
sf_freelist_head.body.links.prev points to the last node in the list. Inserting into and deleting from a circular doubly linked list is done in
the usual way, except that, owing to the use of the sentinel, there are no edge cases for inserting or removing at the beginning or the end of the
list. If you need a further introduction to this data structure, you can readily find information on it by googling ("circular doubly linked lists with
sentinel").
You will also see the following declarations:
#define NUM QUICK LISTS 10 /* Number of quick lists. */
Free List Heads
3/15/2019 CSE 320 / hw3-doc · GitLab
https://gitlab02.cs.stonybrook.edu/cse320/hw3-doc 8/12
#define NUM_QUICK_LISTS 10 / Number of quick lists. /
#define QUICK_LIST_MAX 5 /* Maximum number of blocks permitted on a single quick list. */
struct {
int length; // Number of blocks currently in the list.
struct sf_block *first; // Pointer to first block in the list.
} sf_quick_lists[NUM_QUICK_LISTS];
The array sf_quick_lists gives the heads of the quick lists, of which there are a total of NUM_QUICK_LISTS . At index 0 in this array is the head
of the quick list for blocks of size MIN_BLOCK_SIZE , and for each successive entry in the array the block size increases by the alignment
granularity of 16. The sf_quick_lists array therefore has space for the heads of NUM_QUICK_LISTS quick lists, with sizes ranging from
MIN_BLOCK_SIZE to MIN_BLOCK_SIZE + (NUM_QUICK_LISTS-1) * 16 , in increments of 16. Besides giving a pointer first to the first block in a
quick list, each entry of sf_quick_lists contains a length field that is to be kept updated with the current length of the list headed by that
entry. In contrast to the main free list, the quick lists are maintained as singly linked lists. When a block is in a quick list, only its next pointer is
used. Double linking is not needed, because entries are only ever added or removed at the front of a list.
😱You MUST use the sf_free_list_head variable as the head of your "main free list" and you MUST maintain this as a circular,
doubly linked list. You MUST also maintain the quick lists as singly linked lists and you must access them using a LIFO discipline. The
helper functions discussed later, as well as the unit tests, will assume that you have done this when accessing your free lists.
Your heap should use a prologue and epilogue (as described in the book) to arrange for the proper block alignment and to avoid edge cases
when coalescing blocks. The overall organization of the heap is as shown below:
Format of the heap
+-----------------------------------------------------------------------------------------+
| 64-bits wide |
+-----------------------------------------------------------------------------------------+
heap start
+-----------------------------------------------------------------------------------------+ <- (aligned)
| |
| unused | padding
| 64 bits |
+--------------------------------------------+------------------------+---------+---------+
| unused | block_size (= 32) |prv alloc| alloc | prologue
| | (2 LSB's implicitly 0) | (0) | (1) | header
| 32 bits | 32 bits | 1 bit | 1 bit |
+--------------------------------------------+------------------------+---------+---------+ <- (aligned)
| |
| unused | padding
| 64 bits |
+--------------------------------------------+--------------------------------------------+
| |
| unused | padding
| 64 bits |
+--------------------------------------------+------------------------+---------+---------+ <- (aligned)
| unused | block_size (= 32) |prv alloc| alloc |
| | (2 LSB's implicitly 0) | (0) | (1) | prologue
| 32 bits | 32 bits | 1 bit | 1 bit | footer
+-----------------------------------------------------------------------------------------+
| |
| |
| |
| |
| Allocated and free blocks |
| |
| |
| |
+---------------------------------------------------------------------+---------+---------+
| unused | block_size (= 0) |prv alloc| alloc |
| | (2 LSB's implicitly 0) | (0/1) | (1) | epilogue
| 32 bits | 32 bits | 1 bit | 1 bit |
+---------------------------------------------------------------------+---------+---------+ <- heap end
(aligned)
NOTE: Prologue footer contents must always be identical to prologue header contents,
including "unused" fields.
The "prologue" consists of padding (to achieve the required alignment) and an allocated block with just a header and a footer and a minimumsize payload area, which is unused.
Overall Structure of the Heap: Prologue and Epilogue
3/15/2019 CSE 320 / hw3-doc · GitLab
https://gitlab02.cs.stonybrook.edu/cse320/hw3-doc 9/12
The "epilogue" consists only of an allocated footer, with block size set to 0. The prologue and epilogue are never freed. When the heap is
extended, a new epilogue is created at the end of the newly added region and the old epilogue becomes the header of the new block. This is as
described in the book.
As your heap is initially empty, at the time of the first call to sf_malloc you will need to make one call to sf_mem_grow to obtain a page of
memory within which to set up the prologue and initial epilogue. The remainder of the memory in this first page should then be inserted into
the free list as a single block.
When implementing your sf_malloc function, first determine if the request size is 0. If so, then return NULL without setting sf_errno . If the
request size is non-zero, then you should determine the size of the block to be allocated by adding the header size and the size of any necessary
padding to reach a size that is a multiple of 16 to maintain proper alignment. Remember also that the block has to be big enough to store the
footer and next and prev pointers when it is free, though as these fields are not present in an allocated block this space can (and should) be
overlapped with the payload area. These constraints lead to a minimum block size of 32 bytes, so you should not attempt to allocate any block
smaller than this. After having determined the required block size, you should examine the corresponding quick list (if any) to see if there is any
block of an exactly matching size. If there is, then you should remove and return the first such block. If there is no exactly matching block in the
quick lists, then you should do a first fit search of the main free list. If a big enough block is found, then after splitting it (if it will not leave a
splinter), you should insert the remainder part into the main freelist (note: do not put the remainder obtained when splitting into a quick list)
and return the payload pointer to the first part. If there is no block big enough in the main free list, then you must use sf_mem_grow to request
more memory. (For requests larger than a page, more than one such call might be required). If your allocator ultimately cannot satisfy the
request, your sf_malloc function must set sf_errno to ENOMEM and return NULL .
After each call to sf_mem_grow , you must attempt to coalesce the newly allocated page with any free block immediately preceding it, in order to
build blocks larger than one page. Insert the new block at the beginning of the free list.
Note: Do not coalesce with the prologue or past the beginning of the heap.
When implementing sf_free , you must first verify that the pointer being passed to your function belongs to an allocated block. This can be
done by examining the fields in the block header and footer. In this assignment, we will consider the following cases for invalid pointers:
The pointer is NULL .
The allocated bit in the header is 0.
The header of the block is before the end of the prologue, or after the beginning of the epilogue.
The block_size field is not a multiple of 16 or is less than the minimum block size of 32 bytes. NOTE: It is always a multiple of 16
The requested_size field, plus the size required for the block header, is greater than the block_size field.
If the prev_alloc field is 0, indicating that the previous block is free, then the alloc fields of the previous block header and footer should
also be 0.
If an invalid pointer is passed to your function, you must call abort to exit the program. Use the man page for the abort function to learn
more about this.
After confirming that a valid pointer was given, you must free the block. If there is a quick list corresponding to the block size, then insert the
block at the head of that quick list, assuming that the quick list does not already have QUICK_LIST_MAX blocks in it. If it does, then first "flush"
the quick list by removing all the blocks in it and inserting them into the main free list, coalescing them if possible. Then insert the block being
freed into the now-empty quick list.
😱 Blocks added to a quick list are free to satisfy further allocation requests, but the THIS_BLOCK_ALLOCATED bit should not be
cleared. This is to prevent blocks in quick lists from being coalesced with other blocks in the main free list. When quick list is flushed, the
blocks removed from the quick list should have the THIS_BLOCK_ALLOCATED bit cleared before adding them to the main free list, so
that they can be coalesced.
If there is no quick list corresponding to the size of a block being freed, then the block is simply added directly to the main free list, where it is
subject to coalescing.
When implementing your sf_realloc function, you must first verify that the pointer and size parameters passed to your function are valid. The
criteria for pointer validity are the same as those described in the 'Notes on sf_free' section above. If the pointer is valid but the size parameter is
0, free the block and return NULL .
After verifying both parameters, consider the cases described below. Note that in some cases, sf_realloc is more complicated than calling
sf_malloc to allocate more memory, memcpy to move the old memory to the new memory, and sf_free to free the old memory.
When reallocating to a larger size, always follow these three steps:
Notes on sf_malloc
Notes on sf_mem_grow
Notes on sf_free
Notes on sf_realloc
Reallocating to a Larger Size
3/15/2019 CSE 320 / hw3-doc · GitLab
https://gitlab02.cs.stonybrook.edu/cse320/hw3-doc 10/12
1. Call sf_malloc to obtain a larger block.
2. Call memcpy to copy the data in the block given by the client to the block returned by sf_malloc .
3. Call sf_free on the block given by the client (coalescing if necessary).
4. Return the block given to you by sf_malloc to the client.
If sf_malloc returns NULL , sf_realloc must also return NULL . Note that you do not need to set sf_errno in sf_realloc because
sf_malloc should take care of this.
When reallocating to a smaller size, your allocator must use the block that was passed by the caller. You must attempt to split the returned
block. There are two cases for splitting:
Splitting the returned block results in a splinter. In this case, do not split the block. Leave the splinter in the block, update the header field if
necessary, and return the same block back to the caller.
Example:
b b
+----------------------+ +------------------------+
| allocated | | allocated. |
| Blocksize: 64 bytes | sf_realloc(b, 32) | Block size: 64 bytes |
| payload: 48 bytes | | payload: 32 bytes |
| | | |
| | | |
+----------------------+ +------------------------+
In the example above, splitting the block would have caused a 16-byte splinter. Therefore, the block is not split. The requested_size field in the
footer is set to 32.
The block can be split without creating a splinter. In this case, split the block and update the block size fields in both headers. Free the
remaining block by inserting it into the main free list (coalescing, if possible). Do not insert split blocks into a quick list. Return a pointer to
the payload of the now-smaller block to the caller.
Note that in both of these sub-cases, you return a pointer to the same block that was given to you.
Example:
b b
+----------------------+ +------------------------+
| allocated | | allocated | free |
| Blocksize: 64 bytes | sf_realloc(b, 16) | 32 bytes | 32 bytes. |
| payload: 48 bytes | | payload: | |
| | | 16 bytes | goes into |
| | | | free list |
+----------------------+ +------------------------+
The sfutil library additionally contains the following helper functions, which should be self explanatory. They all output to stderr .
void sf_show_header(sf_header *hp);
void sf_show_block(sf_block *bp);
void sf_show_blocks();
void sf_show_free_list();
void sf_show_quick_lists();
void sf_show_heap();
We have provided these functions to help you visualize your free lists and allocated blocks.
Make sure that memory returned to the client is aligned and padded correctly for the system we use (64-bit Linux Mint).
We will not grade using Valgrind. However, you are encouraged to use it to detect alignment errors.
Reallocating to a Smaller Size
Helper Functions
Things to Remember
Unit Testing
3/15/2019 CSE 320 / hw3-doc · GitLab
https://gitlab02.cs.stonybrook.edu/cse320/hw3-doc 11/12
For this assignment, we will use Criterion to test your allocator. We have provided a basic set of test cases and you will have to write your own as
well.
You will use the Criterion framework alongside the provided helper functions to ensure your allocator works exactly as specified.
In the tests/sfmm_tests.c file, there are ten unit test examples. These tests check for the correctness of sf_malloc , sf_realloc , and
sf_free . We provide some basic assertions, but by no means are they exhaustive. It is your job to ensure that your header/footer bits are set
correctly and that blocks are allocated/freed as specified.
When you compile your program with make , a sfmm_tests executable will be created in the bin folder alongside the main executable. This
can be run with bin/sfmm_tests . To obtain more information about each test run, you can use the verbose print option: bin/sfmm_tests --
verbose=0 .
The first test malloc_an_Integer_check_freelist tests sf_malloc . It allocates space for an integer and assigns a value to that space. It then
runs an assertion to make sure that the space returned by sf_malloc was properly assigned.
cr_assert(*x == 4, "sf_malloc failed to give proper space for an int!");
The string after the assertion only gets printed to the screen if the assertion failed (i.e. *x != 4 ). However, if there is a problem before the
assertion, such as a SEGFAULT, the unit test will print the error to the screen and continue to run the rest of the unit tests.
For this assignment you must write 5 additional unit tests which test new functionality and add them to sfmm_tests.c below the following
comment:
//############################################
//STUDENT UNIT TESTS SHOULD BE WRITTEN BELOW
//DO NOT DELETE THESE COMMENTS
//############################################
For additional information on Criterion library, take a look at the official documentation located here! This documentation is VERY
GOOD.
Make sure your directory tree looks like this and that your homework compiles.
.
├── .gitlab-ci.yml
└── hw3
├── include
│ ├── debug.h
│ └── sfmm.h
├── lib
│ └── sfutil.o
├── Makefile
├── src
│ ├── main.c
│ └── sfmm.c
└── tests
└── sfmm_tests.c
This homework's tag is: hw3
$ git submit hw3
🤓 This program will be very difficult to get working unless you are extremely disciplined about your coding style. Think carefully
about how to modularize your code in a way that makes it easier to understand and avoid mistakes. Verbose, repetitive code is errorprone and evil! When writing your program try to comment as much as possible. Format the code consistently. It is much easier for
your TA and the professor to help you if we can quickly figure out what your code does.
Compiling and Running Tests
Writing Criterion Tests
Hand-in instructions