BEST代写-线上留学生作业代写 & 论文代写专家


C操作系统代写 | CS 2110 Homework 10

C操作系统代写 | CS 2110 Homework 10


CS 2110 Homework 10 Implementing Malloc

1 Overview 1.1 Purpose

The purpose of this assignment is to give you a deeper understanding of some of the most important functions in C: malloc, free, calloc, and realloc. These four functions are key to writing programs that can handle dynamic amounts of data, like strings of arbitrary lengths and practically unlimited amounts of user input. Knowing how to use these functions is vital, but it is also important to understand how they work–especially if you are a Devices, Info Internetworks, or Systems/Architecture student who will be taking CS 2200 (and possibly also CS 3210) in a later semester.

1.2 Tasks

You will be implementing the backend of the four core functions for dynamic allocation: malloc, free, calloc, and realloc. While calloc and realloc can be implemented in terms of malloc and free, malloc and free must be implemented from scratch, using a freelist of pointers to keep track of available memory and the sbrk function to obtain more memory when needed.

There are also several helper functions included that you may want to implement. These functions are not graded, but we may provide test cases that help ensure your implementations of these functions are sound. You are not required to use and/or complete any of the helper functions, although you may find the homework a lot easier to complete if you do.

1.3 Criteria

You will be graded using an autograder with several test cases, similar to Homework 9. Each of the four functions will be tested with cases that test different behaviors; for example, one case might expect malloc to find and return a perfectly sized free block, while other cases expect malloc to split a larger block into two.

2 Assignment

In this assignment, you will be writing the dynamic memory allocation and deallocation functions of malloc, free, realloc, and calloc. These functions are confusing to write, so we have provided an in-depth guide below. Please read through this entire pdf before beginning. The specifics for each function are located in malloc.c as well as in the subsections below.

2.1 The Basics

It is the job of the memory allocator to process and satisfy the memory requests of the user. But where does the allocator get its memory? Let us recall the structure of a program’s memory footprint.

+——————-+ (low memory) | CODE | +——————-+
| DATA | +——————-+ <– Break || || +——————-+

                           |       STACK       |
                           +-------------------+ (high memory)

When a program is loaded into memory there are various “segments” created for different purposes: code, stack, data, etc. In order to create some dynamic memory space, otherwise known as the heap, it is possible to move the “break”, which is the first address after the end of the process’s uninitialized data segment. A function called brk() is provided to set this address to a different value. There is also a function called sbrk() which moves the break by some amount specified as a parameter.

                           +-------------------+ (low memory)
                           |       CODE        |
                           |       DATA        |

| HEAP | +——————-+ <– New Break || || +——————-+
| STACK | +——————-+ (high memory)

For simplicity, a wrapper for the system call sbrk() has been provided for you as a function called my sbrk located in suites/malloc suite.c. Make sure to use this call rather than a real call to sbrk, as doing this can potentially cause a lot of problems during program execution. Note that any problems introduced by calling the real sbrk will not be regraded, so make sure that everything is correct before turning in.

If you glance at the code for my sbrk(), you will quickly notice that upon the first call it always allocates 8 KiB. For the purposes of your program, you should treat the returned amount as whatever you requested. For instance, the first time I call my sbrk() it will be done like this:

                      my_sbrk(SBRK_SIZE); /* SBRK_SIZE == 2 KB */

| 8KB | —————————————–
\______ The pointer returned to me by my_sbrk

Even though you have a full 8 KiB, you should treat it as if you were only returned SBRK SIZE bytes. Now when you run out of memory and need more heap space you will need to call my sbrk() again. Once again, the call is simply:



—————————————– |2KB| 6KB | —————————————–

                             \____ The pointer returned to me by my_sbrk

Notice how it returned a pointer to the address after the end of the 2 KB I had requested the first time. my sbrk() remembers the end of the data segment you request each time and is able to return that value to you as the beginning of the new data segment on a following call. Keep this in mind as you write the assignment!

We’ve written my sbrk to be able to only hand out a certain amount of memory before returning -1 to indicate that its done. This limit gives us the ability to test the behavior of the code when my sbrk can’t get more memory.

2.2 Block Allocation

Trying to use sbrk() (or brk()) exclusively to provide dynamic memory allocation to your program would be very difficult and inefficient. Calling sbrk() involves a decent amount of system overhead, and we would prefer not to have to call it every single time a small amount of memory is required. In addition, deallocation would be a problem. Say we allocated several 100 byte chunks of memory and then decided we were done with the first. Where would the break be? There’s no handy function to move the break back, so how could we reuse that first 100 byte chunk?

What we need are a set of functions that manage a pool of memory allowing us to allocate and deallocate efficiently. Typically, such schemes start out with no free memory at all. The first time the user requests memory, the allocator will call sbrk() as discussed above to obtain a relatively large chunk of memory. The user will be given a block with as much free space as they requested, and if there is any memory left over it will be managed by placing information about that left over block of memory in a data structure where information about all such free blocks is kept. This is called the freelist and we will return to this later.

In order to keep track of allocated blocks we will create a structure to store the information we need to know about a block. Where should we store this structure? We can’t simply call malloc() to allocate space, since we’re writing the function, and that’d lead to infinite recursion! However, there’s an easier way that will keep our bookkeeping structure right with the data we’re allocating for easy access.

In order to keep track of allocated blocks, we will create a structure to store the information we need to know about a block, also known as metadata, inside the block itself. The metadata contains two things: a pointer to the next node in the freelist, and the size of the user data section. Both of these are required in order to accurately keep track of the memory available in the freelist.

Figure 1. The metadata is placed before the user data. The next byte after the end of the metadata is the first byte that can be given to the user.

We will need to take into consideration the leading metadata whenever we allocate blocks. To let the user have as much space as they requested, when they request a block of size n bytes we will allocate a block of size sizeof(the metadata) + n. The size requested by the user will be stored in the metadata; additionally, the metadata will contain a pointer to the next metadata struct in the freelist. As depicted in my malloc.h, this is the struct definition for the metadata:


User Data


                             typedef struct metadata {
                                 struct metadata *next_size;
                                 unsigned long size;
                             } metadata_t;

The size portion of the metadata struct contains the size that the user requested. In order to get the total size of the block, we add this size with sizeof(metadata_t), which is the size in bytes of the metadata. For ease of reading, this size will be represented as TMS (total metadata size) in all of our block representation diagrams. The user does not care about the metadata for the block, they just want the size they requested. Therefore, when you return a block to the user, you will need to use pointer arithmetic to ’step over’ the metadata and return the address of the data. What this looks like:

Pointer returned to the user

Figure 2. When a block is returned to the user, the pointer returned points to the beginning address of the area used by the user.

2.3 The Freelist

When we split up memory, we give one piece/block to the user. The remaining pieces/blocks are placed in a linked list, called the freelist, to be used at a later time. For this semester, we are representing our freelist as a single singly linked list that is organized by the address in ascending order. This linked list will be defined as a global file variable and to help you out, we have already defined it for you.


User Data

                                  metadata_t *addr_list;

To help visualize this, below we have an example representation of our freelist.

Block A Meta Size: TMS

addr list Usable Size: 3 Total:3+TMS

block in use by the user

Block B Meta Size: TMS Usable Size: 30


block in use by the user

Block C Meta Size: TMS Usable Size: 10


Note: The name of the blocks refer to their address order. For example, since the letter B comes after the letter A, Block B starts at an address after Block A.

For the remainder of the pdf, we will represent the freelist without spaces for the blocks currently in use by the user like so:

Block A Meta Size: TMS

  1. First Line: The name of the block (“Block B”) – Note that the name refers to the ordering that the blocks should be in.
  2. Second Line: Meta Size → The size of the metadata for that block
  3. Third Line: Usable Size → The size of the space available to the user
  4. Fourth Line: Total → The total size of the memory taken up by this block

Block B Meta Size: TMS Usable Size: 30

A Quick Note: The node representations in our freelists should be read as the following:

addr list Usable Size: 3 Total:3+TMS

Block C Meta Size: TMS Usable Size: 10