COMP3511 Operating System (Spring 2022)
PA3: Simplified malloc/free
Released on 19-Apr-2022 (Tuesday) Due on 10-May-2022 (Tuesday) at 23:59
Introduction
The aim of this project is to help students understand memory management in Linux
operating system. Upon completion of the project, students should be able to write their
own memory management functions: mm_malloc() and mm_free(), and get familiar
with a number of related Linux system calls, such as sbrk().
Program Usage
You need to implement a system program named as vmm to simulate several memory
allocations and deallocations without using the corresponding C standard library functions.
In other words, you are going to write your own version of malloc and free.
Here is a sample usage of vmm:
$> ./vmm < input.txt > output.txt
$> represents the shell prompt.
< means input redirection. > means output redirection. Thus, you can easily use the given
test cases to test your program and use the diff command to compare the output files.
Getting Started
vmm_skeleton.c is provided. You should rename the file as vmm.c
Necessary data structures, variables and several helper functions (e.g. linked list operations
and mm_print()) are already implemented in the provided base code. Instead of
reinventing the wheels, please read carefully the starter code.
Restrictions
Please note that you CANNOT invoke any dynamic memory allocation functions in the C
standard library (), such as malloc(), calloc(), realloc(),
free(), because these library functions will change the heap and will affect our own
memory management implementation.
Zero marks will be given if any of the above dynamic memory allocation function is used.
The grader will check your code.
Page 1 of 8
Project TA - Peter CHUNG (cspeter@cse.ust.hk): Handling questions before the project deadline
Grader TA - Kaiqiang (kxuar@cse.ust.hk): Grading and appeal handling after the deadline
Page 2 of 8
The Input Format
An input file stores several memory allocations and memory deallocations, one operation
per line. You can assume the input sequence is valid.
If the input line is for memory allocation, it should have 2 input parameters:
malloc [name:char] [size:int]
• name is a character ranging from a to z (lower-case).
• size is a positive integer indicating the number of bytes to be allocated
If the input line is for memory deallocation, it should follow with 1 input parameter:
free [name:char]
• name is a character ranging from a to z (lowercase)
Here is an example containing one memory allocation and one memory deallocation. It
allocates 1000 bytes to a pointer a, and then free the pointer a
malloc a 1000
free a
The Output Format
After each step, you should print out the current memory layout with the help of the given
mm_print function.
Here is the sample output of the above 2 operations:
=== malloc a 1000 ===
Block 01: [OCCP] size = 1000 bytes
=== free a ===
Block 01: [FREE] size = 1000 bytes
Project TA - Peter CHUNG (cspeter@cse.ust.hk): Handling questions before the project deadline
Grader TA - Kaiqiang (kxuar@cse.ust.hk): Grading and appeal handling after the deadline
Virtual Memory Address Space
Each process has its own virtual memory address space. To build our own memory allocator,
we need to understand how different parts of a process (e.g., heap, stack, …) are being
mapped in the virtual address space. The layout is as follows:
sbrk() system call
The heap is a continuous virtual memory address space with 3 main regions.
We only focus on the mapped region (i.e., the green region in the above figure):
• The mapped region is defined by 2 pointers:
o the start of the heap
o the current break (brk)
• The current break can be adjusted using system calls such as sbrk()
• To get the current break address, you can invoke sbrk(0)
Heap Data Structure
The following data structure is given in the base code. Please DON’T make any changes:
struct
__attribute__((__packed__)) // compiler directive, avoid "gcc" padding bytes
meta_data {
size_t size; // 8 bytes (in 64-bit OS)
char free; // 1 byte ('f' or 'o')
struct meta_data *next; // 8 bytes (in 64-bit OS)
struct meta_data *prev; // 8 bytes (in 64-bit OS)
};
// calculate the meta data size and store as a constant (exactly 25 bytes)
const size_t meta_data_size = sizeof(struct meta_data);
By default, the gcc compiler adds extra bytes to a struct (e.g., 32 bytes, instead of 25 bytes,
will be used for the above struct). A compiler directive is added to the struct to avoid the
compiler padding extra bytes. Padding bytes is a technique to scarify some bytes to make
copying operations consistent and efficient. In this project, we would like to be accurate.
Thus, by adding the compiler directive, the meta data size is exactly equal to 25 bytes.
Page 3 of 8
Project TA - Peter CHUNG (cspeter@cse.ust.hk): Handling questions before the project deadline
Grader TA - Kaiqiang (kxuar@cse.ust.hk): Grading and appeal handling after the deadline
Linked List Data Structure
In this assignment, we need to implement a linked list to keep track of the memory
allocation. When we allocate a memory block, we need to first allocate the meta data and
then fill in the details of the meta data. For each block, we should include the followings:
• size: the number of bytes for the allocated memory
• free: f means the block is free, and o means the block is occupied
• prev, next: pointers to the previous and the next block
Here is the graphical illustration. Please note that the linked list is an in-place linked list. You
need to be familiar with pointer arithmetic and type casting to calculate the correct pointer
position of each memory block.
A doubly linked list with a dummy head node and several helper functions of linked list are
implemented:
// Global variables
void *start_heap = NULL;
// pointing to the start of the heap, initialize in main()
struct meta_data dummy_head_node;
// dummy head node of a doubly linked list, initialize in main()
struct meta_data *head = &dummy_head_node;
// The implementation of the following functions are given:
void list_add(struct meta_data *new, struct meta_data *prev, struct
meta_data *next);
void list_add_tail(struct meta_data *new, struct meta_data *head);
void init_list(struct meta_data *list);
Page 4 of 8
Project TA - Peter CHUNG (cspeter@cse.ust.hk): Handling questions before the project deadline
Grader TA - Kaiqiang (kxuar@cse.ust.hk): Grading and appeal handling after the deadline
Page 5 of 8
The Starting Pointing
You only need to complete the following missing parts:
void *mm_malloc(size_t size) {
// TODO: Complete mm_malloc here
return NULL;
}
void mm_free(void *p) {
// TODO: Complete mm_free here
}
Implementation of mm_malloc
void *mm_malloc(size_t size);
The input argument, size, is the number of bytes to be allocated from the heap. You can
assume size is positive. Please ensure that the returned pointer is pointing to the
beginning of the allocated space, not the start address of the meta data block.
Iterating the linked list to find the first-fit free block with the following situations:
• If no sufficiently large free block is found, we use sbrk to allocate more space. After
that, we fill in the details of a new block of meta data and then update the linked list
• If the first free block is big enough to be split, we split it into two blocks: one block to
hold the newly allocated memory block, and a residual free block.
• If the first free block is not big enough to be split, occupy the whole free block, and
don’t split.
o Some memory will be wasted (i.e., internal fragmentation)
o In this project, we don’t need to handle the internal fragmentation problem.
Project TA - Peter CHUNG (cspeter@cse.ust.hk): Handling questions before the project deadline
Grader TA - Kaiqiang (kxuar@cse.ust.hk): Grading and appeal handling after the deadline
Implementation of mm_free
void mm_free(void *p);
Deallocate the input pointer, p, from the heap. In our algorithm, we iterate the linked list
and compare the address of p with the address of the data block. If it matches, we mark the
free attribute of struct meta_data from ‘o’ (OCCP) to ‘f’ (FREE) and return.
To simplify the requirements of this project, we don’t need to release the actual memory
back to the operating system (i.e., you don’t need to decrease the current break of the
heap).
In addition, we don’t need to consider the problem of memory fragmentation, which may
be a serious issue if we allocate/deallocate small memory blocks for many times.
Compilation
The following command can be used to compile the program
$> gcc -std=c99 -o vmm vmm.c
The option c99 is used to provide a more flexible coding style (e.g., you can define an
integer variable anywhere within a function)
Sample test cases
10 pair of test cases are provided (i.e., inX.txt and outX.txt, where X=01-10). We don’t have
other hidden test cases.
The grader TA will probably write a grading script to mark the test cases. Please use the
Linux diff command to compare your output with the sample output. For example:
$> diff --side-by-side your-outX.txt sample-outX.txt
Development Environment
CS Lab 2 is the development environment. Please use one of the following machines
(csl2wkXX.cse.ust.hk), where XX=01…40. The grader TA will use the same platform
to grade all submissions.
In other words, “my program works on my own laptop/desktop computer, but not in one of
the CS Lab 2 machines” is an invalid appeal reason. Please test your program on our
development environment (not on your own desktop/laptop) thoughtfully
Page 6 of 8
Project TA - Peter CHUNG (cspeter@cse.ust.hk): Handling questions before the project deadline
Grader TA - Kaiqiang (kxuar@cse.ust.hk): Grading and appeal handling after the deadline
Page 7 of 8
Marking Scheme
1. (100%) Correctness of the 10 pairs of test cases. We don’t have other hidden test
cases, but we will check the source codes to avoid students hard coding the test
cases in their programs. Example of hard coding: a student may simply detect the
input and then display the corresponding output without implementing the program
2. Make sure you use the Linux diff command to check the output format.
3. Make sure to test your program in one of our CS Lab 2 machines (not your own
desktop/laptop computer)
4. Please fill in your name, ITSC email, and declare that you do not copy from others. A
template is already provided near the top of the source file.
Zero marks will be given if malloc(), calloc(), realloc(), free(), or any
other related dynamic memory allocation techniques are used. The reason is that it is
meaningless to write your own malloc using an existing malloc function. During the grading,
the usage of malloc can be easily detected by first removing the comment lines in your
source file, and then search for the above keywords using regular expression.
Zero marks will be given for the plagiarism cases
Plagiarism: Both parties (i.e., students providing the codes and students copying the codes)
will receive 0 marks. Near the end of the semester, a plagiarism detection software (MOSS)
will be used to identify cheating cases. DON’T do any cheating!
Zero marks will be given if the file cannot be graded.
The grader TA cannot grade any submission with compilation errors in our CS Lab 2
machine. In the past semesters, some students submitted the executable file instead of the
source file. The grader TA cannot grade the executable file.
Project TA - Peter CHUNG (cspeter@cse.ust.hk): Handling questions before the project deadline
Grader TA - Kaiqiang (kxuar@cse.ust.hk): Grading and appeal handling after the deadline
Submission
File to submit:
vmm.c
Please check carefully you submit the correct file.
In the past semesters, some students submitted the executable file instead of the source
file. Zero marks will be given as the grader cannot grade the executable file.
You are not required to submit other files, such as the input test cases.
Late Submission
For late submission, please submit it via email to the grader TA.
There is a 10% deduction, and only 1 day late is allowed
(Reference: Chapter 1 of the lecture notes)
Page 8 of 8