Implemented a segregated free list allocator for the x86-64 architecture that manages up to 4 pages of memory at a time.

Author

All works were solely done by Wonyong Jeong except the base code that is designed under the course CSE320: System Fundamentals II led by Professor Jeniffer Wong-Ma and Professor Eugene Stark.

NOTE: If you are a student in such a class, you should not copy (or copy then modify) this code without permission.

Description

Dynamic memory allocatiors including wyjeong_malloc, wyjeong_realloc, and wyjeong_free were implemented in C using the four explicit free lists with a first-fit placement policy and immediate coalescing on free with blocks at higher memory addresses. Free blocks are inserted into the proper free list in last in first out (LIFO) order.

NOTE: considered a word as 2 bytes (16 bits), a memory row as 4 words (64 bits), and a page of memory to be 4096 bytes (4 KB)

Implmentations

Policies Applied

1. Segregated Free List Management Policy

Four segregated free list is used to manage free blocks. The sizes of the blocks in the free lists are decided by the max size macros defined in include/sfmm.h.

2. Block Placement Policy

When allocating memory, I used first fit placement to select the first block in the appropriate sized list. If the program connot find a block that fits in its list, continue searching the larger lists.

3. Immediate Coalescing

The immediate coalescing with blocks of higher memory addresses on free was applied.

4. Splitting Blocks & Splinters

Splitting blocks was implemented to reduce the amount of internal fragmentation. Splinters are small blocks (< 32 bytes in our case) left after splitting a free block. To avoid this, allocator “over allocate”s the amount of memory requested so that these splinters are not inserted into your free lists. If splitting a block would create a splinter, leave the splinter as part of the block.

5. Block Headers & Footers

In this project, the header is 4 words (i.e. 64 bits or 1 memory row).

Padding occurs when the allocated payload size is greater than the requested size. Note that this includes splinters and extra memory for alignment.

Block Header Format:

+--------------------------------------------+------------------+-------+-------+---------+
|                 unused                     |   block_size     |       | padded|  alloc  |
|                                            |                  |  00   |   1   |    1    |
|                 32 bits                    |     28 bits      |       |  bit  |   bit   |
+--------------------------------------------+------------------+-------+-------+---------+

Block Footer Format:

+--------------------------------------------+------------------+-------+-------+---------+
|              requested_size                |   block_size     |       | padded|  alloc  |
|                                            |                  |  00   |   1   |    1    |
|                 32 bits                    |     28 bits      |       |  bit  |   bit   |
+--------------------------------------------+------------------+-------+-------+---------+

6. Memory Row Size

Each “memory row” was assumed as 64-bits in size. The table below lists the sizes of data types 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

7. Free List Heads

typedef struct {
    wyjeong_free_header *head;
    uint16_t min;
    uint16_t max;
} free_list;

extern free_list seg_free_list[FREE_LIST_COUNT];

The free_list struct represents a single free list. It has a pointer to the head of the list as well as the minimum and maximum sizes for blocks in the list. Both sizes are inclusive.

The extern line declares an array of four free_list instances. There is one instance for each free list. Each struct in the array is initialized in src/sfmm.c with a NULL pointer for the free list head and the appropriate min/max block sizes.

Followings represent the general format for memory blocks in the allocator.

#define HEADER_UNUSED_BITS 32
#define BLOCK_SIZE_BITS 28
#define TWO_ZEROES 2
#define PADDED_BITS 1
#define ALLOCATED_BITS 1
#define REQUESTED_SIZE_BITS 32


#define SF_HEADER_SIZE (HEADER_UNUSED_BITS + BLOCK_SIZE_BITS + TWO_ZEROES    \
                        + PADDED_BITS + ALLOCATED_BITS)

#define SF_FOOTER_SIZE SF_HEADER_SIZE

/*

                                      Format of a memory block
    +-----------------------------------------------------------------------------------------+
    |                                       64-bits wide                                      |
    +-----------------------------------------------------------------------------------------+

    +--------------------------------------------+------------------+-------+-------+---------+ <- header
    |                 unused                     |   block_size     |       | padded|  alloc  |
    |                                            |                  |  00   |   1   |    1    |
    |                 32 bits                    |     28 bits      |       |  bit  |   bit   |
    +--------------------------------------------+------------------+-------+-------+---------+
    |                                                                                         | Content of
    |                                   Payload and Padding                                   | the payload
    |                                     (N Memory Rows)                                     |
    |                                                                                         |
    |                                                                                         |
    +--------------------------------------------+------------------+-------+-------+---------+ <- footer
    |              requested_size                |   block_size     |       | padded|  alloc  |
    |                                            |                  |  00   |   1   |    1    |
    |                 32 bits                    |      28 bits     |       |  bit  |   bit   |
    +--------------------------------------------+------------------+-------+-------+---------+
*/

The block header is defined as:

typedef struct {
    uint64_t      allocated : ALLOCATED_BITS;
    uint64_t         padded : PADDED_BITS;
    uint64_t     two_zeroes : TWO_ZEROES;
    uint64_t     block_size : BLOCK_SIZE_BITS;
    uint64_t         unused : HEADER_UNUSED_BITS;
} __attribute__((packed)) sf_header;

To assist in accessing the next and previous pointers of a free block, an additional struct wyjeong_free_header is defined.

struct wyjeong_free_header{
    sf_header header;
    struct wyjeong_free_header *next;
    struct wyjeong_free_header *prev;
};

typedef struct wyjeong_free_header wyjeong_free_header;

Lastly, include/sfmm.h also provides a struct for accessing the footer.

typedef struct {
    uint64_t      allocated : ALLOCATED_BITS;
    uint64_t         padded : PADDED_BITS;
    uint64_t     two_zeroes : TWO_ZEROES;
    uint64_t     block_size : BLOCK_SIZE_BITS;
    uint64_t requested_size : REQUESTED_SIZE_BITS;
} __attribute__((packed)) sf_footer;

Implementation Details

1. wyjeong_malloc

When implementing the wyjeong_malloc function, the program first determines if the request size is valid. The request size is invalid if it is 0 or it is greater than the amount of memory the allocator has access to (4 pages). In the case of an invalid request, set sf_errno to EINVAL and return NULL.

Once the request has been validated, it should add the sizes of the header and footer, as well as any necessary padding to find the necessary block size. It starts searching in the appropriate list, but it must search the next lists in order if it cannot find a block. If a block is not found in any list, it must use sf_sbrk to request more memory. If the allocator cannot satisfy the request, its function sets sf_errno to ENOMEM and returns NULL.

2. wyjeong_free

When implementing wyjeong_free, the allocator first verifies 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 project, I considered the following cases for invalid pointers:

If an invalid pointer is passed to the function, it must call abort to exit the program. I used the man page for the abort function to learn more about this.

After confirming that a valid pointer was given, it must free the block. First, it determines if the “next” block in memory can be coalesced. If it can, removes the “next” block from its free list and combine the blocks. Then, it determines which list the newly freed block should be placed into. It inserts it at the head of this list.

3. wyjeong_realloc

When implementing the wyjeong_realloc function, it first verifies 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 wyjeong_free section above. If the size is 0, free the block and return NULL.

After verifying both parameters, it considers the cases described below. Note that in some cases, wyjeong_realloc is more complicated than calling wyjeong_malloc to allocate more memory, memcpy to move the old memory to the new memory, and wyjeong_free to free the old memory.

1) Reallocating to a Larger Size

When reallocating to a larger size, always follow these three steps:

  1. Call wyjeong_malloc to obtain a larger block

  2. Call memcpy to copy the data in the block given by the user to the block returned by wyjeong_malloc

  3. Call wyjeong_free on the block given by the user (coalescing if necessary)

  4. Return the block given to you by wyjeong_malloc to the user

If wyjeong_malloc returns NULL, wyjeong_realloc must also return NULL. Note that the allocator do not need to set sf_errno in wyjeong_realloc because wyjeong_malloc should take care of this.

2) Reallocating to a Smaller Size

When reallocating to a smaller size, the allocator must use the block that was returned by the user. It must attempt to split the returned block. There are two cases for splitting:

Example:

            b                                        b
+----------------------+                       +------------------------+
| allocated            |                       |   allocated.           |
| Blocksize: 64 bytes  |   wyjeong_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.

Note that in both of these sub-cases, it returns a pointer to the same block that was given to it.

Example:

            b                                        b
+----------------------+                       +------------------------+
| allocated            |                       | allocated |  free      |
| Blocksize: 64 bytes  |   wyjeong_realloc(b, 16)   | 32 bytes  |  32 bytes. |
| payload: 48 bytes    |                       | payload:  |            |
|                      |                       | 16 bytes  | goes into  |
|                      |                       |           | free list 1|
+----------------------+                       +------------------------+

Helper Functions

The sfutil library additionally contains the following helper functions:

These functions helps visualize the free lists and allocated blocks provided by the base code.

Source Code

Source code will be public on my github accout soon.