Description
In this assignment, you will develop a C program to implement the “malloc”, “free”, “calloc” and “realloc”
functionalities.
Instructions:
1. Check out the malloc tutorial from Dan Luu (at Microsoft) on how these functions can be
implemented at: http://danluu.com/malloc-tutorial/
For your convenience, it is also appended in this file. The tutorial implements working
versions of malloc, free, calloc and realloc and you can use that code as-is.
2. Write a driver function (i.e., main function) to demonstrate the usage and efficiency of these functions. The
main() should have at least 10 calls each to malloc, calloc and realloc and at least 5 calls to free. Set up the
function to print out the heap start/end addresses and also print out the memory leaks in your code.
3. Your main task is to implement the exercises mentioned in the tutorial. These are also shown below:
(a) malloc is supposed to return a pointer “which is suitably aligned for any built-in type”.
Does our malloc do that? If so, why? If not, fix the alignment. Note that “any built-in type” is
basically up to 8 bytes for C.
(b) The implemented malloc is really wasteful if we try to re-use an existing block and we
don’t need all of the space. Implement a function that will split up blocks so that they use the
minimum amount of space necessary
(c) After doing (b), if we call malloc and free lots of times with random sizes, we’ll end up
with a bunch of small blocks that can only be re-used when we ask for small amounts of
space. Implement a mechanism to merge adjacent free blocks together so that any consecutive
free blocks will get merged into a single block.
(d) The current implementation implements a first fit algorithm for finding free blocks.
Implement a best fit algorithm instead.
(e) Find and resolve any bugs in the existing code!
4. Repeat Step (2) with this implementation to demonstrate usage of the functions and memory leakage.
5. Your code must use the set-up mentioned in this tutorial. Other online resources can be consulted but NOT
copied. The tutorial mentions some other implementations for splitting/merging blocks that can only be
consulted but not copied.
To turn in:
1. You will need 4 files: (a) a header file with all the function prototypes, (b) a .c file with all the function
definitions, (c) a .c file with the driver main() function and (d) a Makefile to compile your code. Note that you only
2
need to submit the improved versions of the functions and not the preliminary implementations from the tutorial.
Additionally, include a text file mentioning which portions of your code are working and which portions don’t and
why.
2. Create a tarball file with all these files. Upload the program on BlackBoard by the assignment deadline
(11:59pm of the day of the assignment). The tarball should be named LASTNAME-EID-assign2.tgz,
where LASTNAME is your last name in all capital letters and EID is your VCU E-ID.
Note: Late assignments will lose 5 points per day upto a maximum of 3 days. Code must be submitted in the
prescribed format.
For questions on grading, contact the grader: Syed Khajamoinuddin <lnusk@mymail.vcu.edu>
Aquick tutorial on implementing and debugging malloc, free,calloc, and realloc
Let’s writea mallocand see howit works with existing programs!
This tutorialis going to assumethat you knowwhat pointersare,and that you knowenoughC to knowthat *ptr dereferencesa pointer, ptr->foo
means (*ptr).foo, thatmallocis used to dynamically allocatespace,and that you’refamiliar with theconcept ofalinked list. Fora basicintro to C,
Pointers onC is one ofmy favorite books. If youwant to look atall ofthiscodeat once, it’savailable here.
Preliminariesaside, malloc’s function signatureis
void *malloc(size_t size);
It takesas inputa number of bytesand returnsa pointer to a block ofmemory ofthatsize.
Therearea number ofways wecan implement this. We’re going to arbitrarily chooseto usethesbrk syscall. The OS reserves stack and heap spacefor
processesand sbrk lets us manipulatethe heap. sbrk(0) returnsa pointer to thecurrent top ofthe heap. sbrk(foo) increments the heap size by foo
and returnsa pointer to the previous top ofthe heap.
Ifwe want to implementareally simple malloc, wecan do something like
#include <assert.h>
#include <string.h>
#include <sys/types.h>
#include <unistd.h>
void *malloc(size_t size) {
void *p = sbrk(0);
void *request = sbrk(size);
if (request == (void*) -1) {
return NULL; // sbrk failed.
} else {
assert(p == request); // Not thread safe.
return p;
}
}
When a programasks mallocfor space, mallocasks sbrk to increment the heap sizeand returnsa pointer to thestart ofthe newregion on the heap. This
is missing atechnicality, that malloc(0) should either return NULL oranother pointer thatcan be passed to free withoutcausing havoc, but it basically
works.
Butspeaking offree, howdoes free work? Free’s prototypeis
void free(void *ptr);
When freeis passed a pointer that was previously returned frommalloc, it’s supposed to freethespace. But given a pointer to something allocated by our
malloc, we have no idea whatsize block isassociated with it. Where do westorethat?Ifwe had a workingmalloc, wecould mallocsomespaceand
storeit there, but we’re going to run into troubleifwe need to callmallocto reservespaceeach time wecallmallocto reservespace.
Acommon trick to work around this is to store meta-information abouta memory region in somespacethat wesquirrelaway just belowthe pointer that
wereturn. Say thetop ofthe heap iscurrently at 0x1000 and weask for 0x400 bytes. Ourcurrentmalloc willrequest 0x400 bytes fromsbrk and return
a pointer to 0x1000. Ifweinstead save, say, 0x10 bytes to storeinformation about the block, our malloc would request 0x410 bytes fromsbrk and
return a pointer to 0x1010, hiding our 0x10 byte block ofmeta-information fromthecodethat’scallingmalloc.
That lets us freea block, but thenwhat? The heap regionwe get fromthe OS has to becontiguous, so wecan’t return a block ofmemory in the middleto
converted by Web2PDFConvert.com
the OS. Even ifwe were willing to copy everything abovethe newly freed region down to fillthe hole, so wecould return spaceat theend, there’s no way
to notify all ofthecode with pointers to the heap that those pointers need to beadjusted.
Instead, wecanmark that the block has been freed without returning it to the OS, so that futurecalls to malloccan usere-usethe block. But to do that
we’ll need beableto access the metainformation foreach block. Therearealot of possiblesolutions to that. We’llarbitrarily chooseto useasinglelinked
list for simplicity.
So, foreach block, we’llwant to havesomething like
struct block_meta {
size_t size;
struct block_meta *next;
int free;
int magic; // For debugging only. TODO: remove this in non-debug mode.
};
#define META_SIZE sizeof(struct block_meta)
We need to knowthesize ofthe block, whether or not it’s free,and what the next block is. There’sa magic number herefor debugging purposes, but it’s
not really necessary; we’llset it to arbitrary values, whichwilllet useasily see which code modified thestruct last.
We’llalso need a head for our linked list:
void *global_base = NULL;
For our malloc, we’llwant to re-usefreespaceif possible,allocating space whenwecan’t re-useexisting space. Given that we havethis linked list
structure,checking ifwe haveafree block and returning it is straightforward. Whenwe getarequest ofsomesize, weiteratethrough our linked list to see
ifthere’safree block that’s largeenough.
struct block_meta *find_free_block(struct block_meta **last, size_t size) {
struct block_meta *current = global_base;
while (current && !(current->free && current->size >= size)) {
*last = current;
current = current->next;
}
return current;
}
Ifwe don’t find afree block, we’ll haveto requestspacefromthe OS using sbrk and add our newblock to theend ofthelinked list.
struct block_meta *request_space(struct block_meta* last, size_t size) {
struct block_meta *block;
block = sbrk(0);
void *request = sbrk(size + META_SIZE);
assert((void*)block == request); // Not thread safe.
if (request == (void*) -1) {
return NULL; // sbrk failed.
}
if (last) { // NULL on first request.
last->next = block;
}
block->size = size;
block->next = NULL;
block->free = 0;
block->magic = 0x12345678;
return block;
}
As with our originalimplementation, werequestspace using sbrk. But weadd a bit ofextraspaceto store our struct,and then set thefields ofthestruct
appropriately.
Nowthat we have helper functions to check ifwe haveexisting freespaceand to requestspace, our mallocis simple. If our global base pointer is NULL,
we need to requestspaceand set the base pointer to our newblock. Ifit’s not NULL, wecheck to seeifwecan re-useany existing space. Ifwecan, then
we do; ifwecan’t, thenwerequestspaceand usethe newspace.
void *malloc(size_t size) {
struct block_meta *block;
// TODO: align size?
if (size <= 0) {
return NULL;
}
if (!global_base) { // First call.
block = request_space(NULL, size);
if (!block) {
converted by Web2PDFConvert.com
return NULL;
}
global_base = block;
} else {
struct block_meta *last = global_base;
block = find_free_block(&last, size);
if (!block) { // Failed to find free block.
block = request_space(last, size);
if (!block) {
return NULL;
}
} else { // Found free block
// TODO: consider splitting block here.
block->free = 0;
block->magic = 0x77777777;
}
}
return(block+1);
}
Foranyone who isn’t familiar withC, wereturn block+1 because we want to return a pointer to theregion after block_meta. Since block isa pointer of
type struct block_meta, +1 increments theaddress by one sizeof(struct(block_meta)).
Ifwejust wanted a malloc withoutafree, wecould have used our original, much simpler malloc. So let’s writefree! The main thing free needs to do is set
->free.
Because we’ll need to get theaddress of our struct inmultiple places in ourcode, let’s definethis function.
struct block_meta *get_block_ptr(void *ptr) {
return (struct block_meta*)ptr – 1;
}
Nowthat we havethat, here’s free:
void free(void *ptr) {
if (!ptr) {
return;
}
// TODO: consider merging blocks once splitting blocks is implemented.
struct block_meta* block_ptr = get_block_ptr(ptr);
assert(block_ptr->free == 0);
assert(block_ptr->magic == 0x77777777 || block_ptr->magic == 0x12345678);
block_ptr->free = 1;
block_ptr->magic = 0x55555555;
}
In addition to setting ->free, it’s valid to callfree with a NULL ptr, so we need to check for NULL. Sincefreeshouldn’t becalled on arbitrary addresses
or on blocks thatarealready freed, wecan assert that thosethings never happen.
You never really need to assertanything, but it oftenmakes debugging aloteasier. In fact, when I wrotethiscode, I had a bug that would haveresulted in
silent datacorruption iftheseasserts weren’t there. Instead, thecodefailed at theassert, whichmakeit trivialto debug.
Nowthat we’ve gotmallocand free, wecanwrite programs using ourcustommemory allocator! But before wecan drop ourallocator into existing code,
we’ll need to implementacouple morecommon functions, reallocand calloc. Callocis justmallocthat initializes the memory to 0, so let’s look at realloc
first. Reallocis supposed to adjust thesize ofa block ofmemory that we’ve gotten frommalloc,calloc, or realloc.
Realloc’s function prototypeis
void *realloc(void *ptr, size_t size)
Ifwe pass realloca NULL pointer, it’s supposed to act just like malloc. Ifwe pass ita previouslymalloced pointer, itshould free up spaceifthesizeis
smaller than the previous size,and allocate morespaceand copy theexisting data over ifthesizeis larger than the previous size.
Everythingwillstillwork ifwe don’t resize when thesizeis decreased and we don’t freeanything, but weabsolutely haveto allocate morespaceifthesize
is increased, so let’s start with that.
void *realloc(void *ptr, size_t size) {
if (!ptr) {
// NULL ptr. realloc should act like malloc.
return malloc(size);
}
struct block_meta* block_ptr = get_block_ptr(ptr);
if (block_ptr->size >= size) {
// We have enough space. Could free some once we implement split.
converted by Web2PDFConvert.com
return ptr;
}
// Need to really realloc. Malloc new space and free old space.
// Then copy old data to new space.
void *new_ptr;
new_ptr = malloc(size);
if (!new_ptr) {
return NULL; // TODO: set errno on failure.
}
memcpy(new_ptr, ptr, block_ptr->size);
free(ptr);
return new_ptr;
}
And nowforcalloc, which justclears the memory beforereturning a pointer.
void *calloc(size_t nelem, size_t elsize) {
size_t size = nelem * elsize; // TODO: check for overflow.
void *ptr = malloc(size);
memset(ptr, 0, size);
return ptr;
}
Notethat this doesn’tcheck for overflowin nelem * elsize, which isactually required by thespec. All ofthecode hereis justenough to getsomething
that kindasorta works.
Nowthat we havesomething that kinda works, wecan use our with existing programs (and we don’teven need to recompilethe programs)!
First, we need to compile ourcode. On linux, something like
clang -O0 -g -W -Wall -Wextra -shared -fPIC malloc.c -o malloc.so
should work.
-g adds debug symbols, so wecan look at ourcode with gdb or lldb. -O0 will help with debugging, by preventing individual variables fromgetting
optimized out. -W -Wall -Wextra addsextra warnings. -shared -fPIC willlet us dynamically link ourcode, which is what lets us use ourcode with
existing binaries!
Onmacs, we’llwantsomething like
clang -O0 -g -W -Wall -Wextra -dynamiclib malloc.c -o malloc.dylib
Notethat sbrk is deprecated on recent versions ofOS X. Apple usesan unorthodox definition of deprecated – some deprecated syscallsare badly
broken. I didn’t really test this on a Mac, so it’s possiblethat this willcause weird failures or or just not work on a mac.
Now, to use geta binary to use our malloc on linux, we’ll need to set the LD_PRELOAD environment variable. If you’re using bash, you can do that with
export LD_PRELOAD=/absolute/path/here/malloc.so
If you’ve gota mac, you’llwant
export DYLD_INSERT_LIBRARIES=/absolute/path/here/malloc.so
Ifeverythingworks, you can run somearbitrary binary and it willrun as normal(except that it will bea bitslower).
$ ls
Makefile malloc.c malloc.so README.md test test-0 test-1 test-2 test-3 test-4
Ifthere’sa bug, youmight getsomething like
$ ls
Segmentation fault (core dumped)
Debugging
Let’s talk about debugging! If you’refamiliar with using a debugger to set breakpoints, inspectmemory,and step through code, you can skip this section
and go straight to theexercises.
This section assumes you can figure out howto install gdb on your system. If you’re on a mac, youmaywant to just uselldb and translatethecommands
appropriately. SinceI don’t knowwhat bugs youmight run into, I’mgoing to introduceacouple of bugsand showhowI’d track themdown.
First, we need to figure out howto run gdb without having itsegfault. Ifls segfaults,and wetry to run gdb ls, gdb isalmostcertainly going to segfault,
too. Wecould writea wrapper to do this, but gdb also supports this. Ifwestart gdb and then run set environment LD_PRELOAD=./malloc.so
beforerunning the program, LD_PRELOAD willwork as normal.
converted by Web2PDFConvert.com
$ gdb /bin/ls
(gdb) set environment LD_PRELOAD=./malloc.so
(gdb) run
Program received signal SIGSEGV, Segmentation fault.
0x00007ffff7bd7dbd in free (ptr=0x0) at malloc.c:113
113 assert(block_ptr->free == 0);
Asexpected, we getasegfault. Wecan look around with list to seethecode near thesegfault.
(gdb) list
108 }
109
110 void free(void *ptr) {
111 // TODO: consider merging blocks once splitting blocks is implemented.
112 struct block_meta* block_ptr = get_block_ptr(ptr);
113 assert(block_ptr->free == 0);
114 assert(block_ptr->magic == 0x77777777 || block_ptr->magic == 0x12345678);
115 block_ptr->free = 1;
116 block_ptr->magic = 0x55555555;
117 }
And thenwecan use p (for print) to see what’s going onwith the variables here:
(gdb) p ptr
$6 = (void *) 0x0
(gdb) p block_ptr
$7 = (struct block_meta *) 0xffffffffffffffe8
ptr is 0, i.e., NULL, which is thecause ofthe problem:weforgot to check for NULL.
Nowthat we’vefigured that out, let’s try aslightly harder bug. Let’s say that we decided to replace our struct with
struct block_meta {
size_t size;
struct block_meta *next;
int free;
int magic; // For debugging only. TODO: remove this in non-debug mode.
char data[1];
};
and then return block->data instead of block+1 frommalloc, with no otherchanges. This seems pretty similar to what we’realready doing – wejust
definea member that points to theend ofthestruct,and return a pointer to that.
But here’s what happens ifwetry to use our newmalloc:
$ /bin/ls
Segmentation fault (core dumped)
gdb /bin/ls
(gdb) set environment LD_PRELOAD=./malloc.so
(gdb) run
Program received signal SIGSEGV, Segmentation fault.
_IO_vfprintf_internal (s=s@entry=0x7fffff7ff5f0, format=format@entry=0x7ffff7567370 “%s%s%s:%u: %s%sAssertion `%s’
failed.\n%n”, ap=ap@entry=0x7fffff7ff718) at vfprintf.c:1332
1332 vfprintf.c: No such file or directory.
1327 in vfprintf.c
This isn’tas niceas our lasterror – wecan seethat one of ourasserts failed, but gdb drops us into some print function that’s being called when theassert
fails. But that print function uses our buggymallocand blows up!
Onethingwecould do fromhere would beto inspect ap to see what assert was trying to print:
(gdb) p *ap
$4 = {gp_offset = 16, fp_offset = 48, overflow_arg_area = 0x7fffff7ff7f0, reg_save_area = 0x7fffff7ff730}
That would work fine; wecould pokearound untilwefigure out what’s supposed to get printed and figure out thefailthat way. Some other solutions
would beto write our own customassert or to usetheright hooks to prevent assert fromusing our malloc.
But in thiscase, we knowthereare only afewasserts in ourcode. The oneinmallocchecking that we don’t try to usethis in a multithreaded programand
thetwo in freechecking that we’re not freeing somethingweshouldn’t. Let’s look at freefirst, by setting a breakpoint.
$ gdb /bin/ls
(gdb) set environment LD_PRELOAD=./malloc.so
(gdb) break free
Breakpoint 1 at 0x400530
(gdb) run /bin/ls
Breakpoint 1, free (ptr=0x61c270) at malloc.c:112
converted by Web2PDFConvert.com
112 if (!ptr) {
block_ptr isn’tset yet, but ifwe use s afewtimes to step forward to after it’s set, wecan see what the valueis:
(gdb) s
(gdb) s
(gdb) s
free (ptr=0x61c270) at malloc.c:118
118 assert(block_ptr->free == 0);
(gdb) p/x *block_ptr
$11 = {size = 0, next = 0x78, free = 0, magic = 0, data = “”}
I’musing p/x instead of p so wecan seeit in hex. The magic field is 0, which should beimpossiblefora valid struct that we’retrying to free. Maybe
get_block_ptr is returning a bad offset? We have ptr availableto us, so wecan just inspect different offsets. Sinceit’sa void *, we’ll haveto cast it
so that gdb knows howto interpret theresults.
(gdb) p sizeof(struct block_meta)
$12 = 32
(gdb) p/x *(struct block_meta*)(ptr-32)
$13 = {size = 0x0, next = 0x78, free = 0x0, magic = 0x0, data = {0x0}}
(gdb) p/x *(struct block_meta*)(ptr-28)
$14 = {size = 0x7800000000, next = 0x0, free = 0x0, magic = 0x0, data = {0x78}}
(gdb) p/x *(struct block_meta*)(ptr-24)
$15 = {size = 0x78, next = 0x0, free = 0x0, magic = 0x12345678, data = {0x6e}}
Ifwe back offa bit fromtheaddress we’re using, wecan seethat thecorrect offset is 24 and not 32. What’s happening hereis thatstructs get padded, so
that sizeof(struct block_meta) is 32,even though thelast valid member isat 24. Ifwe want to cut out thatextraspace, we need to fix
get_block_ptr.
That’s it for debugging!
Exercises
Personally, this sort ofthing never sticks withme unless I work through someexercsies, so I’llleaveacoupleexercises hereforanyone who’s interested.
1. mallocis supposed to return a pointer“which is suitably aligned forany built-in type”. Does our malloc do that?Ifso, why?If not, fix thealignment.
Notethat“any built-in type”is basically up to 8 bytes for C because SSE/AVXtypesaren’t built-in types.
2. Our mallocis reallywastefulifwetry to re-usean existing block and we don’t need all ofthespace. Implementafunction that willsplit up blocks so
that they usethe minimumamount ofspace necessary
3. After doing 2, ifwecallmallocand freelots oftimes with randomsizes, we’llend up with a bunch ofsmall blocks thatcan only bere-used whenwe
ask for smallamounts ofspace. Implementa mechanismto mergeadjacent free blocks together so thatany consecutivefree blocks will getmerged
into asingle block.
4. Find bugs in theexisting code! I haven’t tested this much, so I’msurethereare bugs,even ifthis basically kindasorta works.
Resources
I read this tutorial byMarwanBurelle beforesitting down and trying to write my own implementation, so it’s pretty similar. The main implementaiton
differencesarethatmy version is simpler, butmore vulnerableto memory fragmentation. In terms ofexposition, my styleisalotmorecasual. If youwant
something a bitmoreformal, Dr. Burelle has you covered.
For more on howLinux deals withmemorymanagement, seethis post byGustavo Duarte.
For more on howreal-world mallocimplementations work, dlmallocand tcmallocare both great reading. I haven’t read thecodefor jemalloc,and I’ve
heard that it’sa bitmore more difficult to understand, but it’salso the most widely used high-performance mallocimplementation around.
For help debugging, Address Sanitizer isamazing. If youwant to writeathread-safe version, Thread Sanitizer isalso a great tool.
There’saspanish translation ofthis post herethanks to Matias GarciaIsaia.
Acknowledgements
Thanks to Gustavo Duartefor lettingme use one of his images to illustratesbrk, to IanWhitlock and Danielle Sucher for finding sometypos, to Nathan
Kurzfor suggestions on additionalresources,and to “tedu”forcatching a bug. Pleaseletme knowif you find other bugs in this post (whether they’rein the
writing or thecode).
← The performancecost of integer overflow checking
Theef ect of markets on discrimination is more nuanced than you think →
converted by Web2PDFConvert.com
Archive Popular About (hire me!)
Twitter RSS
converted by Web2PDFConvert.com