Starting from:
$30
CSE320- Dynamic Memory Allocation Solved
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.
Immediate coalescing of blocks on free with adjacent free 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.
Obfuscation of block footers to detect attempts to free blocks not previously obtained via allocation.
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.
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). The size classes are based on powers of 2, according to the following: 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 whose size is in the interval (M, 2M] . The third list holds blocks whose size is in the interval (2M, 4M] . The fourth list holds blocks whose size is in the interval (4M, 8M] , and so on. This pattern continues up to the interval
(64M, 128M] , and then the last list holds all blocks of size greater than 128M . Allocation requests will be satisfied by searching the free lists in increasing order of size class. Each individual free list will be organized as a circular, doubly linked list (more information below).
Block Placement Policy
When allocating memory in response to an allocation request, use a segregated fits policy 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 free list that contains a sufficiently large block, then sf_mem_grow should be called to extend the heap by an additional page of memory. After coalescing this page (see below) 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.
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.
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. Note that, as a result of alignment and overhead constraints, 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.
Freeing a Block
When a block is freed, 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.
Block Headers & Footers
typedef struct sf_block { sf_footer prev_footer; // NOTE: This actually belongs to the *previous* 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]; // Length varies according to block size. } 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.
Logically, the footer contents of a block are always to be maintained identical to the header contents (and this is how they are shown in the diagrams above). However, as a security feature to help catch freeing of invalid blocks, what will actually be stored in the footer field is the bitwise XOR (C operator ^ ) of the header contents with a "magic number" that is obtained by calling sf_magic() . The magic number is set upon initialization of the heap and it will be different from one execution to the next. This is intended to make it difficult to free a block (either inadvertently or maliciously) that was not previously obtained from malloc() .
☹☺☷☶☳☴☵☸ Note that the prev_footer field is actually part of the previous block in the heap. In order to initialize an sf_block pointer to correctly access the fields of a block, it is necessary to compute the address of the footer of the immediately preceding block in the heap and then cast that address to type sf_block * . The footer of a particular block can be obtained by first getting an sf_block * pointer for that block and then using the contained information (i.e. the block size) to obtain the prev_footer field
of the next block in the heap. The sf_block structure has been specified this way so as to permit it to be defined with a fixed size, even though the payload size is unknown and will vary.
Free List Heads
In the file include/sfmm.h , you will see the following declaration:
#define NUM_FREE_LISTS 8
struct sf_block sf_free_list_heads[NUM_FREE_LISTS];
The array sf_free_list_heads contains the heads of the free lists, which are maintained as circular, doubly linked lists. Each node in a free list contains a next pointer that points to the next node in the list, and a prev pointer that points the previous node. For each index i with 0 <= i < NUM_FREE_LISTS the variable sf_free_list_head[i] is a dummy, "sentinel" node, which is used to connect the
beginning and the end of the list at index i . This sentinel 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_heads[i].body.links.next and
sf_freelist_heads[i].body.links.prev both contain &sf_freelist_heads[i] (i.e. the sentinel node points back to itself). If the list is
nonempty, then sf_freelist_heads[i].body.links.next points to the first node in the list and
sf_freelist_heads[i].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 MUST use the sf_free_list_heads array for the heads of your free lists and you MUST maintain these lists as circular, doubly linked lists. The helper functions discussed later, as well as the unit tests, will assume that you have done this when accessing your free lists.
sf_footer footer;
} sf_prologue;
/* Structure of the epilogue. */ typedef struct sf_epilogue { sf_header header;
} sf_epilogue;
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.
Notes on sf_malloc
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 (which will always be present), as well as the next and prev pointers when the block is free. As the next and
prev pointers are not present in an allocated block this space can (and should) be overlapped with the payload area. The above
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 determine the smallest free list that would be able to satisfy a request of that size. Search that free list from the beginning until the first sufficiently large block is found. If there is no such block, continue with the next larger size class. If a big enough block is found, then after splitting it (if it will not leave a splinter), you should insert the remainder part back into the appropriate freelist. When splitting a block, the "lower part" should be used to satisfy the allocation request and the "upper part" should become the remainder. If there is no block big enough in any freelist, 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 .
Notes on sf_mem_grow
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 appropriate free list.
Note: Do not coalesce with the prologue or epilogue, or past the beginning or end of the heap.
Notes on sf_free
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 to be 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 the footer of the block is after the beginning of the epilogue.
The block_size field is less than the minimum block size of 32 bytes.
The prev_alloc field is 0, indicating that the previous block is free, but the alloc field of the previous block header is not 0.
The bitwise XOR of the footer contents and the value returned by sf_magic() does not equal the header contents.
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. First, the block must be coalesced with any adjacent free block. Then, determine the size class appropriate for the (now-coalesced) block and inserting the block at the beginning of the free list for that size class. Note that blocks in a free list must not be marked as allocated.
Notes on sf_realloc
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
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.
Immediate coalescing of blocks on free with adjacent free 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.
Obfuscation of block footers to detect attempts to free blocks not previously obtained via allocation.
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.
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). The size classes are based on powers of 2, according to the following: 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 whose size is in the interval (M, 2M] . The third list holds blocks whose size is in the interval (2M, 4M] . The fourth list holds blocks whose size is in the interval (4M, 8M] , and so on. This pattern continues up to the interval
(64M, 128M] , and then the last list holds all blocks of size greater than 128M . Allocation requests will be satisfied by searching the free lists in increasing order of size class. Each individual free list will be organized as a circular, doubly linked list (more information below).
Block Placement Policy
When allocating memory in response to an allocation request, use a segregated fits policy 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 free list that contains a sufficiently large block, then sf_mem_grow should be called to extend the heap by an additional page of memory. After coalescing this page (see below) 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.
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.
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. Note that, as a result of alignment and overhead constraints, 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.
Freeing a Block
When a block is freed, 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.
Block Headers & Footers
typedef struct sf_block { sf_footer prev_footer; // NOTE: This actually belongs to the *previous* 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]; // Length varies according to block size. } 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.
Logically, the footer contents of a block are always to be maintained identical to the header contents (and this is how they are shown in the diagrams above). However, as a security feature to help catch freeing of invalid blocks, what will actually be stored in the footer field is the bitwise XOR (C operator ^ ) of the header contents with a "magic number" that is obtained by calling sf_magic() . The magic number is set upon initialization of the heap and it will be different from one execution to the next. This is intended to make it difficult to free a block (either inadvertently or maliciously) that was not previously obtained from malloc() .
☹☺☷☶☳☴☵☸ Note that the prev_footer field is actually part of the previous block in the heap. In order to initialize an sf_block pointer to correctly access the fields of a block, it is necessary to compute the address of the footer of the immediately preceding block in the heap and then cast that address to type sf_block * . The footer of a particular block can be obtained by first getting an sf_block * pointer for that block and then using the contained information (i.e. the block size) to obtain the prev_footer field
of the next block in the heap. The sf_block structure has been specified this way so as to permit it to be defined with a fixed size, even though the payload size is unknown and will vary.
Free List Heads
In the file include/sfmm.h , you will see the following declaration:
#define NUM_FREE_LISTS 8
struct sf_block sf_free_list_heads[NUM_FREE_LISTS];
The array sf_free_list_heads contains the heads of the free lists, which are maintained as circular, doubly linked lists. Each node in a free list contains a next pointer that points to the next node in the list, and a prev pointer that points the previous node. For each index i with 0 <= i < NUM_FREE_LISTS the variable sf_free_list_head[i] is a dummy, "sentinel" node, which is used to connect the
beginning and the end of the list at index i . This sentinel 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_heads[i].body.links.next and
sf_freelist_heads[i].body.links.prev both contain &sf_freelist_heads[i] (i.e. the sentinel node points back to itself). If the list is
nonempty, then sf_freelist_heads[i].body.links.next points to the first node in the list and
sf_freelist_heads[i].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 MUST use the sf_free_list_heads array for the heads of your free lists and you MUST maintain these lists as circular, doubly linked lists. The helper functions discussed later, as well as the unit tests, will assume that you have done this when accessing your free lists.
sf_footer footer;
} sf_prologue;
/* Structure of the epilogue. */ typedef struct sf_epilogue { sf_header header;
} sf_epilogue;
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.
Notes on sf_malloc
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 (which will always be present), as well as the next and prev pointers when the block is free. As the next and
prev pointers are not present in an allocated block this space can (and should) be overlapped with the payload area. The above
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 determine the smallest free list that would be able to satisfy a request of that size. Search that free list from the beginning until the first sufficiently large block is found. If there is no such block, continue with the next larger size class. If a big enough block is found, then after splitting it (if it will not leave a splinter), you should insert the remainder part back into the appropriate freelist. When splitting a block, the "lower part" should be used to satisfy the allocation request and the "upper part" should become the remainder. If there is no block big enough in any freelist, 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 .
Notes on sf_mem_grow
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 appropriate free list.
Note: Do not coalesce with the prologue or epilogue, or past the beginning or end of the heap.
Notes on sf_free
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 to be 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 the footer of the block is after the beginning of the epilogue.
The block_size field is less than the minimum block size of 32 bytes.
The prev_alloc field is 0, indicating that the previous block is free, but the alloc field of the previous block header is not 0.
The bitwise XOR of the footer contents and the value returned by sf_magic() does not equal the header contents.
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. First, the block must be coalesced with any adjacent free block. Then, determine the size class appropriate for the (now-coalesced) block and inserting the block at the beginning of the free list for that size class. Note that blocks in a free list must not be marked as allocated.
Notes on sf_realloc
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
1 file (794.1KB)
