Second project

netID: aha6793

Should be around 150 lines of code

CSE 3320 Project 2 (Spring 2024)
Due date: 11:59pm 4/21 (Sunday) (upload one .zip file in Canvas)
In this assignment you will build your own implementation of malloc() and free(). That is, you
will implement a library that interacts with the operating system to perform heap management on
behalf of a user process.
Connect to the Omega server [refer to Project 1 for detail on this step]
$> ssh @omega.uta.edu
Download the code.
$> git clone https://gitlab.com/sjiang-lab/CSE3320-malloc-proj
Build and run the code.
The code compiles into four shared libraries and six test programs. To build the code, first
change to your top-level assignment directory:
$> cd CSE3320-malloc-proj
$> mkdir lib
$> make
Once you have the library, you can use it to override the existing malloc implementation by
using LD_PRELOAD. As an example:
$> env LD_PRELOAD=lib/libmalloc-ff.so tests/ffnf
Here your shared library lib/libmalloc-ff.so contains the malloc() we implemented. When
this malloc() is loaded, it replaces the malloc() implementation in the commonly used libc.so (the
standard malloc()). when the user program tests/ffnf runs and calls malloc(), the new
malloc() is called.
There are four heap management schemes with different strategies (the aforementioned four
shared libraries) to search for available space.
Best-Fit: libmalloc-bf.so
First-Fit: libmalloc-ff.so
Next-Fit: libmalloc-nf.so
Worst-Fit: libmalloc-wf.so
Your programming, experimenting, and reporting tasks:
1. Read the framework of malloc() and free() provided on the course github repository.
(all structs and functions are in the malloc.c file, and complete the “TODO”s in the file).
2. Implement three additional heap management strategies: Next Fit, Worst Fit, Best Fit (First
Fit has already been implemented for you).
3. Each contiguous memory space that is allocated or free in the heap is named a block. Your
program will implement splitting and coalescing of free blocks. If two free blocks are
adjacent, then combine them. If a free block is larger than the requested size, then split the
block into two.
4. Counters exist in the code for tracking of the following events:
Number of times the user calls malloc successfully
Number of times the user calls free successfully
Number of times we reuse an existing block
Number of times we request a new block
Number of times we split a block
Number of times we coalesce blocks
Number blocks in free list
Total amount of memory requested
Maximum size of the heap
The code will print the statistics upon exit and should look like:
mallocs: 8
frees: 8
reuses: 1
grows: 5
splits: 1
coalesces: 1
blocks: 5
requested: 7298
max heap: 4096
Note that these stats are fake ones only for illustration. You will need to increment these counters
where appropriate.
5. Eight test programs are provided to help debug your code. They are located in the tests
directory.
6. Use the malloc() to implement realloc and calloc.
7. You must also benchmark the four implementations of your malloc() against the standard
malloc(). Design and develop a suite of programs and capture execution time for your four
malloc() implementations and compare their performance against the same programs using
the standard malloc(). At a minimum your suite of tests must evaluate the programs based on:
•
•
•
•
Performance
Relative comparison of number of splits and heap growth
Heap fragmentation
Max heap size
8. A report must be generated with the findings. At a minimum the report must contain:
• Executive summary
• Description of the algorithms implemented.
• Test implementation
• Test results for all five candidates (standard malloc and the four additional
implementations)
• Explanation and interpretation of the results including any anomalies in the test results.
• Conclusion. The report must be of a PDF file.
The rubric for grading your report is appended.
Submission:
Your submission will include (1) malloc.c that contains all source code about memory
allocation implementations (Items 1-6) (2) a suite of benchmark programs (named
benchmark-1.c, benchmark-2.c, …). A brief description of the programs should be in the
report. (3) The report in the pdf format. Package all the files in one .zip file and upload it
at Canvas.
Hint
You will see an extra malloc of 1024 bytes in your statistics. This is the space allocated by
printf(). That is, printf() calls the malloc(). For this reason, your malloc() implementation should
not call printf().
Important Warning
This program involves a lot of pointers and pointer arithmetic. You will seg fault your code if
you are not careful with your pointers. Verify ALL pointers pointers before you dereference
them.
Bad: if ( ptr -> next )
Good: if( ptr && ptr->next )
Debugging
While running the tests, you may encounter some segfaults and other memory errors. Because
we are side-loading our own malloc implementation, you will need to do the following to debug
a test application using gdb.
$ gdb ./tests/ffnf
…
(gdb) set exec-wrapper env LD_PRELOAD=./lib/libmalloc-ff.so
(gdb) run
…
(gdb) where
Basically, you want to first load gdb with the test program that is crashing. Next, you need to tell
gdb to utilize the appropriate malloc library by creating an exec-wrapper that loads it into
memory. Next, simply run the program. Once it segfaults, you can print a stack trace by using the
where command. From there, you can explore the state of your program and see if you can
determine what went wrong.
You may also go through the program with gdb line by line and print the value of a variable for
your better understanding of the program. Here is the example:
$ gdb ./tests/ffnf
…
(gdb) set exec-wrapper env LD_PRELOAD=./lib/libmalloc-ff.so
(gdb) b main
Breakpoint 1 at 0x4005c5: file tests/ffnf.c, line 7.
(gdb) r
Starting program: /719740/CSE3320-malloc-proj/./tests/ffnf
Breakpoint 1, main () at tests/ffnf.c:7
7
char * ptr1 = ( char * ) malloc ( 1000 );
(gdb) n
8
char * buf1 = ( char * ) malloc ( 1 );
(gdb) print ptr1
$1 = 0x602018 “”
…
(gdb) n
9
char * ptr6= ( char * ) malloc ( 10 );
(gdb) s
malloc (size=10) at src/malloc.c:173
173
if( atexit_registered == 0 )
(gdb) n
180
size = ALIGN4(size);
Here is the explanation of the command:
b main: set the breakpoint at the main function
n: go to the next line.
print ptr1: print the value of ptr1.
s: step into the function
You can find more commands about `gdb` here.
Grading rubrics for SO 6
Understand
the problem
and identify
evaluation
metrics for
experiments
Acquire and
use software
libraries and
tools needed
for
experiments
Design
experiments
and develop
programs for
evaluation
Use the
developed
programs to
collect
experimental
results
Excellent (5 pts)
Good (4 pts)
Satisfactory (3 pts)
Poor (2 pts)
Unacceptable (1 pt)
All components and
concepts are clearly
understood; identify
appropriate and
comprehensive metrics
for evaluation and
provide good
explanations why the
metrics are chosen
Several options
considered, can discuss
which 2 or 3 were
pursued to trial, why one
was selected
Good understanding of
concepts and of the
system view; identify
some metrics for
evaluation and provide
justifications for metric
selection; however, miss
some key evaluation
metrics
Two or more options for
tools are considered;
small trials with more
than one option are used
to determine suitability
of implementation
Basic understanding of
concepts and
components; identify
some metrics for
evaluation but fail to
justify the selection.
Can restate concepts but
does not understand use
of them in this problem;
fail to identify
appropriate evaluation
metrics
Cannot understand work
requirements and how
experiments need to be
done, cannot identify
concepts needed to be
used in experiment
Unable to understand
what is needed, not able
to find or download
libraries, header files, or
compilers needed
Clearly design
experiments for different
purposes and
evaluations; the
developed programs are
correct, efficient, and
well-documented; the
selection of
programming languages
and environments is
appropriate, and the
results are reproducible.
Clear and systematic
methodology for data
collection; collect
comprehensive results
and present the results in
a clear and
straightforward way
Experiments are welldesigned; the developed
programs are correct, but
efficiency could be
improved; experiment
results are reproducible.
Can find some tools,
libraries and example
code, however there are
mismatches (incorrect
tools for the
environment, or some
important tools are
missing)
Programs are developed Only parts of the
according to the design of experiments are
experiments, but some
conducted; the
designed may not be
developed programs are
well-justified. The
incomplete and often
developed programs are
generate incorrect
mostly correct, but there outputs.
are variations in the
results and some
experiments are not
reproducible in a
different environment
Results have been
Some partial results are
successfully collected but obtained, programs may
some important results
have runtime errors, or
are missing; the collected not generate the needed
results may contain
data
erroneous, inconsistent,
or incomplete data
Data collection is
somewhat ad hoc but no
important result is
missing; Results are
tabulated, but there lacks
visualization to compare
different results
A single set of libraries,
tools and interfaces are
collected, adequate to
create experiment, no
other choices or options
considered
2
Code does not compile or
has runtime error before
any results are generated
No, or insufficient results
are collected from trial
runs
Analyze and
interpret
experimental
results and
draw
conclusions
Data results are well
explained in simple
terms; analysis and
interpretation are clearly
articulated and correct;
conclusions are correct
Analysis and
interpretation are
comprehensive, but some
explanations are not
well-supported by
experimental results;
most conclusions are
correct, but some are not
supported by results
Results are explained and
the interpretation is
mostly correct, but
anomalies are ignored or
incorrectly explained;
conclusions lack
evidence support
3
Results are collected, but
not well-interpreted or
analyzed; no definite
conclusions are made, or
conclusions are mostly
incorrect
No analysis or
interpretation of results
is provided; no
conclusions are made