Starting from:
$24.99
CS/ECE 354, Assignment 5 Memory allocator
CS/ECE 354, Assignment 5
The purpose of this program is to help you understand the nuances of building a memory allocator,
to further increase your C programming skills by
working a lot more with pointers and to get familiar with using Makefiles.
</P
<P
Please read this entire assignment specification before starting
on the first step.
</P
<H3Program Description</H3
<p
For this assignment, you will be given the structure for
a simple shared library that implements
the memory allocation functions
<codemalloc()</code and <codefree()</code.
Everything is present, except for the definitions of those
two functions, called <codeMem_Alloc()</code and <codeMem_Free()</code
in this library.
</p
<h3 Step One: Understand the Code</h3
<p
Memory allocators have two distinct tasks.
First, the memory allocator asks the operating system to expand the heap
portion of the process's address space by calling either <codesbrk()</code or <code
mmap()</code.
Second, the memory allocator doles out this memory to the calling process.
This involves managing a free list of memory and finding a contiguous chunk of
memory that is large enough for the user's request;
when the user later frees memory, it is added back to this list.
</p
<p
This memory allocator is usually provided as part of a standard library,
and it is not part of the OS.
To be clear, the memory allocator operates entirely within
the virtual address space
of a single process and knows nothing about which physical pages have been
allocated to this process or the mapping from logical addresses
to physical addresses.
</p
<p
Classic <codemalloc()</code and <codefree()</code are defined as follows:
</p
<ul
<li
<codevoid *malloc(size_t size)</code:
<codemalloc()</code allocates <codesize</code bytes and returns
a pointer to the allocated memory.
The memory is not cleared.
</li
<li
<codevoid free(void *ptr)</code:
<codefree()</code frees the memory space pointed to by <codeptr</code,
which must have been returned by a previous call to <codemalloc()</code (or <codecalloc()</code or <coderealloc()</code).
Otherwise, or if <codefree(ptr)</code has already been called before,
undefined behavior occurs.
If <codeptr</code is <codeNULL</code, no operation is performed.
</li
</ul
<p
</p
<p
Create a directory for this assignment.
The source code files you will need are in the directory:
</p
<pre
/p/course/cs354-common/public/html/alloc.program/
</pre
<p
Copy the files <codeMakefile</code, <codemem.c</code and <codemem.h</code
to your own directory.
You will probably copy more files for Step 3, but these 3 files
are sufficient for Step 2.
In <codemem.c</code is fully working code for two functions:
<b<codeMem_Init(int sizeOfRegion)</code</b and <b<codeMem_Dump()</code</b.
Look at them, and understand what they do, as well as how they accomplish
their task. Also note the global block header pointer <b<codelist_head</code</b which is the head of our free linked list of memory chunks. Read the header comments for the block header structure provided <bvery carefully</b to understand the convention used.
</p
<ul
<li
<p
<b<codeMem_Init(int sizeOfRegion)</code:</b<br
This sets up and initializes the heap space that the
module manages. <codesizeOfRegion</code is the number of bytes that are requested to be initialized on the heap. <br
This function should be called once at the start of any program before calling any of the other three functions. When testing your code you should call this function first to initialize enough space so that subsequent calls to allocate space via <codeMem_Alloc()</code can be served successfully. The test files we provide (as mentioned below) do the same.<br
Note that <codeMem_Init(int sizeOfRegion)</code rounds up the amount memory requested in units of the page size. <br
Because of rounding up, the amount of memory initialized may be more than <codesizeOfRegion</code. You may use all of this initialized space for allocating memory to the user.<br
Once <codeMem_Init(int sizeOfRegion)</code has been successfully called, <codelist_head</code will be initialized as the first and only header in the free list which points to a single free chunk of memory. You will use this list to allocate space to the user via <codeMem_Alloc()</code calls<br
<codeMem_Init(int sizeOfRegion)</code uses the <codemmap()</code system call to initialize space on the heap. If you are interested, read the man pages to see how that works.
</p
</li
<p
<li
<b<codeMem_Dump()</code:</b<br
This is used for debugging; it prints a list of
all the memory blocks (both free and allocated).
It will be incredibly useful when you are trying to determine if
your code works properly.
As a future programming note: take notice of this function.
When you are working on implementing a complex program,
a function like this that produces lots of useful information about a
data structure can be well worth the time you might spend implementing it.
</p
</li
</ul
<h3 Step Two: Write the Code</h3
<p
<bNote: Do <inot</i change the interface. Do not change anything within
file <codemem.h</code. Do not change any part of functions <codeMem_Init()</code
or <codeMem_Dump()</code.</b
</p
<p
Write the code to implement <codeMem_Alloc()</code and <codeMem_Free()</code.
Use a <bbest fit</b algorithm when allocating blocks with <codeMem_Alloc()</code.
When freeing memory, always <bcoalesce</b with the adjacent memory blocks if they are free.
<codelist_head</code is the free list structure as defined and described in <codemem.c</code
<bIt is based on the model described in your textbook in section 9.9.6 ( except
our implementation has an additional next pointer in the header in order to make it easier to
traverse through the free list structure).</b
Here are definitions for the functions:
</p
<ul
<li
<b<codevoid *Mem_Alloc(int size)</code:</b
<br<codeMem_Alloc()</code is similar to the library function
<codemalloc()</code.
<codeMem_Alloc</code takes as an input parameter the
<codesize</code in bytes of the memory space to be allocated,
and it returns a pointer to the start of that memory space.
The function returns <codeNULL</code if there is not enough
contiguous free space
within <codesizeOfRegion</code allocated by <codeMem_Init</code
to satisfy this request.
For better performance,
<codeMem_Alloc()</code is to return 4-byte aligned chunks of memory.
For example if a user requests 1 byte of memory,
the <codeMem_Alloc()</code implementation should return 4 bytes of memory,
so that the next free block will also be 4-byte aligned.
To debug whether you return 4-byte aligned pointers,
you could print the pointer this way:
<code<pre
printf("%08x", ptr) .
</pre</code
The last digit should be a multiple of 4 (that is, 0, 4, 8, or C).
For example, b7b2c04c is okay, and b7b2c043 is <inot</i okay.
<p Once the best fit free block is located we could use the entire block for the allocation. The disadvantage is that it causes internal fragmentation and wastes space. So we will split the block into two. The first part becomes the allocated block, and the
remainder becomes a new free block. Before splitting the block there should be enough space left over for a new free block i.e the header and its minimum payload of 4 bytes, otherwise we don't split the block.
</p
</li
<li
<b<codeint Mem_Free(void *ptr)</code:</b
<br<codeMem_Free()</code frees the memory object that <codeptr</code points to.
Just like with the standard <codefree()</code,
if <codeptr</code is <codeNULL</code, then no operation is performed.
The function returns 0 on success and -1 if
the <codeptr</code was not allocated by <codeMem_Alloc()</code.
If <codeptr</code is <codeNULL</code, also return -1. For the block being freed, always coalesce with its adjacent blocks if either or both of them are free.
</li
</ul
<h3 Step Three: Test the Code</code</h3
<p
You have a provided <codeMakefile</code that compiles your
code in <codemem.c</code and <codemem.h</code into a shared library
called <codelibmem.so</code.
To do the compilation, the command is
<pre
make mem
</pre
</p
<p
With this shared library, it is time to test if your <codeMem_Alloc()</code
and <codeMem_Free()</code implementations work.
This implies that you will need to write a separate program that
links in your shared library, and makes
calls to the functions within this shared library.
We've already written a bunch of small programs that do this,
to help you get started.
Our programs and a second Makefile are in
</p
<pre
/p/course/cs354-common/public/html/alloc.program/tests/
</pre
<p
Copy all the files within this directory into a
new directory within the one containing your shared library.
Name your new directory <codetests</code.
</p
<p
In this directory, file <codetestlist.txt</code contains a list
of the tests we are giving you to help you start testing your code.
The tests are ordered by difficulty.
<bPlease note that these tests are not sufficient or complete for
testing your code;</b
they are meant to help you get started.
</p
<p
When you run <imake</i within the <codetests</code directory,
it will make executables of all the C programs in this directory.
</p
<!--
The makefile specifies the base name of the library with
the option <code-lmem</code and the path,
so that the linker can find the library "-L.".
<pre
gcc mymain.c -lmem -L. -o myprogram -m32
</pre
--
The linking step needs to use your library, <codelibmem.so</code.
So, you need to tell the linker where to find this file.
Before you run any of the created dynamically linked executables,
you will need to set the environment variable, <codeLD_LIBRARY_PATH</code,
so that the system can find your library at run time.
Assuming you always run a testing executable from (your copy of)
this same <codetests/</code directory,
and the dynamically linked library (<codelibmem.so</code) is
one level up,
that directory (to a Linux shell) is '../', so you can use the command:
<pre
export LD_LIBRARY_PATH=../
</pre
Or, if you use a *csh shell:
<pre
setenv LD_LIBRARY_PATH ${LD_LIBRARY_PATH}:../
</pre
If the setenv command returns an error "LD_LIBRARY_PATH: Undefined variable",
do not panic.
The error implies that your shell has not defined the environment variable.
In this case, run:
<pre
setenv LD_LIBRARY_PATH ../
</pre
</p
<h3 Step Four: Design a New Test</code</h3
<p
Create a new C program that tests whether simple <codeMem_Free()</code
calls work.
The test should determine if a single allocation, followed
by a call to <codeMem_Free()</code does the right thing.
After you have debugged enough to know that it works correctly,
add to this same C program a test case to make sure that <codeMem_Free()</code
does the right thing if passed a bad pointer.
A bad pointer is one with the <codeNULL</code value
or an address of memory space <inot</i allocated by <codeMem_Alloc()</code.
Name this testing program <codefreetests.c</code.
</p
<h3Hints</h3
<ul
<liAlways keep in mind that the value of <codesize_status</code excludes the space for the header block. Make use of <codesizeof(block_header)</code to set the apporpriate size of requested block.</li
<liIt is highly recommended that you write small helper functions(test them first) for common operations and checks such as: isFree, setFree, setAllocated etc.</li
<liDouble check your pointer arithmetic. (int*)+1 changes the address by 4, (void*)+1 or (char*)+1 changes it by 1. What does (block_header*)+1 change it by?</li
<liFor any tests that you write, make sure you call <codeMem_init()</code first to allocate sufficient space.</li
<liCheck return values for all function calls to make sure you don't get unexpected behaviour.</li
</ul
<h3Handing In the Assignment</h3
<pTurn in files <codemem.c</code and <codefreetests.c</code.
Copy these files into your handin directory.
Your handin directory for this project is
<br<code/p/course/cs354-common/public/spring15.handin/<yourloginID/p5/</code
<p<code<yourloginID</code is the username of your CS account.</p
<pYour Handin Folder should have the following files:
<ol
<limem.c</li
<lifreetests.c</li
</ol
</p
<p<iIf you are working as part of a pair</i, you must turn in an extra file. This file will contain the names and sections of <bboth</b students in the pair. As an example, if Kevin worked with Urmish on this assignment, the contents of the extra file for both Kevin and Urmish would be</p
<preKevin Zhang section 1
Urmish Thakker section 2</pre
<pThe name of this file is specialized to help the 354 automated grading tools identify who worked together. This file name is composed of the CS logins of the partners separated by a period. The file name is of the form <login1.<login2. Kevin's login is kzhang, and Urmish's login is uthakker. The file name that both use will be kzhang.uthakker. Please have both partners use the same file name. It does not matter which partner's name is first within this file name.</p
<!--
<p
If you are working with a partner, follow the directions
given in Assignment 3 for the extra file that identifies
partners.
</p
--
<H3Requirements</H3
<ol
<li
Within the comment block at the top of <codemem.c</code,
add a new line of the form:
<pre
* MODIFIED BY: name, section#, partnername, section#
</pre
</li
<li
Your program is to continue the style of the code
already in the file.
Use the same types of comments, and use tabs/spaces as the existing
code does.
</li
<li
Document your added functions with inline comments!
</li
<!--
<li
Use the <bgalapagos</b Linux machines for this assignment!
A penalty will be imposed for any program that was obviously edited
on a Windows machine and transferred to the Unix machines
for turning in.
Text files in Windows have different line endings (^M) at the
end of every line, so check you code on the Linux machines to make sure its in order.
</li
--
<li
Your programs must compile
on the CS Linux lab machines as indicated in this specification
<iwithout warnings or errors</i.
</li
<li
<b
Do <inot</i use any <codestdlib</code allocate or free functions
in this program!
</b
The penalty for using <codemalloc()</code (or friends) will be
no credit for this assignment.
</li
</ol
<h3
The purpose of this program is to help you understand the nuances of building a memory allocator,
to further increase your C programming skills by
working a lot more with pointers and to get familiar with using Makefiles.
</P
<P
Please read this entire assignment specification before starting
on the first step.
</P
<H3Program Description</H3
<p
For this assignment, you will be given the structure for
a simple shared library that implements
the memory allocation functions
<codemalloc()</code and <codefree()</code.
Everything is present, except for the definitions of those
two functions, called <codeMem_Alloc()</code and <codeMem_Free()</code
in this library.
</p
<h3 Step One: Understand the Code</h3
<p
Memory allocators have two distinct tasks.
First, the memory allocator asks the operating system to expand the heap
portion of the process's address space by calling either <codesbrk()</code or <code
mmap()</code.
Second, the memory allocator doles out this memory to the calling process.
This involves managing a free list of memory and finding a contiguous chunk of
memory that is large enough for the user's request;
when the user later frees memory, it is added back to this list.
</p
<p
This memory allocator is usually provided as part of a standard library,
and it is not part of the OS.
To be clear, the memory allocator operates entirely within
the virtual address space
of a single process and knows nothing about which physical pages have been
allocated to this process or the mapping from logical addresses
to physical addresses.
</p
<p
Classic <codemalloc()</code and <codefree()</code are defined as follows:
</p
<ul
<li
<codevoid *malloc(size_t size)</code:
<codemalloc()</code allocates <codesize</code bytes and returns
a pointer to the allocated memory.
The memory is not cleared.
</li
<li
<codevoid free(void *ptr)</code:
<codefree()</code frees the memory space pointed to by <codeptr</code,
which must have been returned by a previous call to <codemalloc()</code (or <codecalloc()</code or <coderealloc()</code).
Otherwise, or if <codefree(ptr)</code has already been called before,
undefined behavior occurs.
If <codeptr</code is <codeNULL</code, no operation is performed.
</li
</ul
<p
</p
<p
Create a directory for this assignment.
The source code files you will need are in the directory:
</p
<pre
/p/course/cs354-common/public/html/alloc.program/
</pre
<p
Copy the files <codeMakefile</code, <codemem.c</code and <codemem.h</code
to your own directory.
You will probably copy more files for Step 3, but these 3 files
are sufficient for Step 2.
In <codemem.c</code is fully working code for two functions:
<b<codeMem_Init(int sizeOfRegion)</code</b and <b<codeMem_Dump()</code</b.
Look at them, and understand what they do, as well as how they accomplish
their task. Also note the global block header pointer <b<codelist_head</code</b which is the head of our free linked list of memory chunks. Read the header comments for the block header structure provided <bvery carefully</b to understand the convention used.
</p
<ul
<li
<p
<b<codeMem_Init(int sizeOfRegion)</code:</b<br
This sets up and initializes the heap space that the
module manages. <codesizeOfRegion</code is the number of bytes that are requested to be initialized on the heap. <br
This function should be called once at the start of any program before calling any of the other three functions. When testing your code you should call this function first to initialize enough space so that subsequent calls to allocate space via <codeMem_Alloc()</code can be served successfully. The test files we provide (as mentioned below) do the same.<br
Note that <codeMem_Init(int sizeOfRegion)</code rounds up the amount memory requested in units of the page size. <br
Because of rounding up, the amount of memory initialized may be more than <codesizeOfRegion</code. You may use all of this initialized space for allocating memory to the user.<br
Once <codeMem_Init(int sizeOfRegion)</code has been successfully called, <codelist_head</code will be initialized as the first and only header in the free list which points to a single free chunk of memory. You will use this list to allocate space to the user via <codeMem_Alloc()</code calls<br
<codeMem_Init(int sizeOfRegion)</code uses the <codemmap()</code system call to initialize space on the heap. If you are interested, read the man pages to see how that works.
</p
</li
<p
<li
<b<codeMem_Dump()</code:</b<br
This is used for debugging; it prints a list of
all the memory blocks (both free and allocated).
It will be incredibly useful when you are trying to determine if
your code works properly.
As a future programming note: take notice of this function.
When you are working on implementing a complex program,
a function like this that produces lots of useful information about a
data structure can be well worth the time you might spend implementing it.
</p
</li
</ul
<h3 Step Two: Write the Code</h3
<p
<bNote: Do <inot</i change the interface. Do not change anything within
file <codemem.h</code. Do not change any part of functions <codeMem_Init()</code
or <codeMem_Dump()</code.</b
</p
<p
Write the code to implement <codeMem_Alloc()</code and <codeMem_Free()</code.
Use a <bbest fit</b algorithm when allocating blocks with <codeMem_Alloc()</code.
When freeing memory, always <bcoalesce</b with the adjacent memory blocks if they are free.
<codelist_head</code is the free list structure as defined and described in <codemem.c</code
<bIt is based on the model described in your textbook in section 9.9.6 ( except
our implementation has an additional next pointer in the header in order to make it easier to
traverse through the free list structure).</b
Here are definitions for the functions:
</p
<ul
<li
<b<codevoid *Mem_Alloc(int size)</code:</b
<br<codeMem_Alloc()</code is similar to the library function
<codemalloc()</code.
<codeMem_Alloc</code takes as an input parameter the
<codesize</code in bytes of the memory space to be allocated,
and it returns a pointer to the start of that memory space.
The function returns <codeNULL</code if there is not enough
contiguous free space
within <codesizeOfRegion</code allocated by <codeMem_Init</code
to satisfy this request.
For better performance,
<codeMem_Alloc()</code is to return 4-byte aligned chunks of memory.
For example if a user requests 1 byte of memory,
the <codeMem_Alloc()</code implementation should return 4 bytes of memory,
so that the next free block will also be 4-byte aligned.
To debug whether you return 4-byte aligned pointers,
you could print the pointer this way:
<code<pre
printf("%08x", ptr) .
</pre</code
The last digit should be a multiple of 4 (that is, 0, 4, 8, or C).
For example, b7b2c04c is okay, and b7b2c043 is <inot</i okay.
<p Once the best fit free block is located we could use the entire block for the allocation. The disadvantage is that it causes internal fragmentation and wastes space. So we will split the block into two. The first part becomes the allocated block, and the
remainder becomes a new free block. Before splitting the block there should be enough space left over for a new free block i.e the header and its minimum payload of 4 bytes, otherwise we don't split the block.
</p
</li
<li
<b<codeint Mem_Free(void *ptr)</code:</b
<br<codeMem_Free()</code frees the memory object that <codeptr</code points to.
Just like with the standard <codefree()</code,
if <codeptr</code is <codeNULL</code, then no operation is performed.
The function returns 0 on success and -1 if
the <codeptr</code was not allocated by <codeMem_Alloc()</code.
If <codeptr</code is <codeNULL</code, also return -1. For the block being freed, always coalesce with its adjacent blocks if either or both of them are free.
</li
</ul
<h3 Step Three: Test the Code</code</h3
<p
You have a provided <codeMakefile</code that compiles your
code in <codemem.c</code and <codemem.h</code into a shared library
called <codelibmem.so</code.
To do the compilation, the command is
<pre
make mem
</pre
</p
<p
With this shared library, it is time to test if your <codeMem_Alloc()</code
and <codeMem_Free()</code implementations work.
This implies that you will need to write a separate program that
links in your shared library, and makes
calls to the functions within this shared library.
We've already written a bunch of small programs that do this,
to help you get started.
Our programs and a second Makefile are in
</p
<pre
/p/course/cs354-common/public/html/alloc.program/tests/
</pre
<p
Copy all the files within this directory into a
new directory within the one containing your shared library.
Name your new directory <codetests</code.
</p
<p
In this directory, file <codetestlist.txt</code contains a list
of the tests we are giving you to help you start testing your code.
The tests are ordered by difficulty.
<bPlease note that these tests are not sufficient or complete for
testing your code;</b
they are meant to help you get started.
</p
<p
When you run <imake</i within the <codetests</code directory,
it will make executables of all the C programs in this directory.
</p
<!--
The makefile specifies the base name of the library with
the option <code-lmem</code and the path,
so that the linker can find the library "-L.".
<pre
gcc mymain.c -lmem -L. -o myprogram -m32
</pre
--
The linking step needs to use your library, <codelibmem.so</code.
So, you need to tell the linker where to find this file.
Before you run any of the created dynamically linked executables,
you will need to set the environment variable, <codeLD_LIBRARY_PATH</code,
so that the system can find your library at run time.
Assuming you always run a testing executable from (your copy of)
this same <codetests/</code directory,
and the dynamically linked library (<codelibmem.so</code) is
one level up,
that directory (to a Linux shell) is '../', so you can use the command:
<pre
export LD_LIBRARY_PATH=../
</pre
Or, if you use a *csh shell:
<pre
setenv LD_LIBRARY_PATH ${LD_LIBRARY_PATH}:../
</pre
If the setenv command returns an error "LD_LIBRARY_PATH: Undefined variable",
do not panic.
The error implies that your shell has not defined the environment variable.
In this case, run:
<pre
setenv LD_LIBRARY_PATH ../
</pre
</p
<h3 Step Four: Design a New Test</code</h3
<p
Create a new C program that tests whether simple <codeMem_Free()</code
calls work.
The test should determine if a single allocation, followed
by a call to <codeMem_Free()</code does the right thing.
After you have debugged enough to know that it works correctly,
add to this same C program a test case to make sure that <codeMem_Free()</code
does the right thing if passed a bad pointer.
A bad pointer is one with the <codeNULL</code value
or an address of memory space <inot</i allocated by <codeMem_Alloc()</code.
Name this testing program <codefreetests.c</code.
</p
<h3Hints</h3
<ul
<liAlways keep in mind that the value of <codesize_status</code excludes the space for the header block. Make use of <codesizeof(block_header)</code to set the apporpriate size of requested block.</li
<liIt is highly recommended that you write small helper functions(test them first) for common operations and checks such as: isFree, setFree, setAllocated etc.</li
<liDouble check your pointer arithmetic. (int*)+1 changes the address by 4, (void*)+1 or (char*)+1 changes it by 1. What does (block_header*)+1 change it by?</li
<liFor any tests that you write, make sure you call <codeMem_init()</code first to allocate sufficient space.</li
<liCheck return values for all function calls to make sure you don't get unexpected behaviour.</li
</ul
<h3Handing In the Assignment</h3
<pTurn in files <codemem.c</code and <codefreetests.c</code.
Copy these files into your handin directory.
Your handin directory for this project is
<br<code/p/course/cs354-common/public/spring15.handin/<yourloginID/p5/</code
<p<code<yourloginID</code is the username of your CS account.</p
<pYour Handin Folder should have the following files:
<ol
<limem.c</li
<lifreetests.c</li
</ol
</p
<p<iIf you are working as part of a pair</i, you must turn in an extra file. This file will contain the names and sections of <bboth</b students in the pair. As an example, if Kevin worked with Urmish on this assignment, the contents of the extra file for both Kevin and Urmish would be</p
<preKevin Zhang section 1
Urmish Thakker section 2</pre
<pThe name of this file is specialized to help the 354 automated grading tools identify who worked together. This file name is composed of the CS logins of the partners separated by a period. The file name is of the form <login1.<login2. Kevin's login is kzhang, and Urmish's login is uthakker. The file name that both use will be kzhang.uthakker. Please have both partners use the same file name. It does not matter which partner's name is first within this file name.</p
<!--
<p
If you are working with a partner, follow the directions
given in Assignment 3 for the extra file that identifies
partners.
</p
--
<H3Requirements</H3
<ol
<li
Within the comment block at the top of <codemem.c</code,
add a new line of the form:
<pre
* MODIFIED BY: name, section#, partnername, section#
</pre
</li
<li
Your program is to continue the style of the code
already in the file.
Use the same types of comments, and use tabs/spaces as the existing
code does.
</li
<li
Document your added functions with inline comments!
</li
<!--
<li
Use the <bgalapagos</b Linux machines for this assignment!
A penalty will be imposed for any program that was obviously edited
on a Windows machine and transferred to the Unix machines
for turning in.
Text files in Windows have different line endings (^M) at the
end of every line, so check you code on the Linux machines to make sure its in order.
</li
--
<li
Your programs must compile
on the CS Linux lab machines as indicated in this specification
<iwithout warnings or errors</i.
</li
<li
<b
Do <inot</i use any <codestdlib</code allocate or free functions
in this program!
</b
The penalty for using <codemalloc()</code (or friends) will be
no credit for this assignment.
</li
</ol
<h3
1 file (15.1KB)
