Project 3a: Malloc and Free
Make sure to read the general instructions for the project here.
Changelog
- Clarified Mem_Available()
- Changed Mem_Free to return -1 if ptr is NULL or invalid. Added example.
- Changed Header max size from 16 to 32 bytes
- Added Extra Credit
- Added Test Information
- Clarified that
Mem_Alloc() can use all the memory mmaped by Mem_Init()
Objectives
There are three objectives to this part of the assignment:
- To understand the nuances of building a memory allocator.
- To do so in a performance-efficient manner.
- To understand how to optimize performance for a given workload.
- To create shared libraries.
- To have fun with a contest! (scroll down for details)
Overview
In this project, you will be implementing a memory allocator for the heap
of a user-level process. Your functions will be to build your own
malloc() and
free() .
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 sbrk or mmap . 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.
This memory allocator is usually provided as part of a standard library and
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; that part is handled by the
operating system.
When implementing this basic functionality in your project, we have a few
guidelines. First, when requesting memory from the OS, you must use
mmap() (which is easier to use than sbrk() ).
Second, although a real memory allocator requests more memory from the OS
whenever it can't satisfy a request from the user, your memory allocator must
call mmap() only one time (when it is first initialized).
Classic malloc() and free() are defined as follows:
void *malloc(size_t size) : malloc() allocates
size bytes and returns a
pointer to the allocated memory. The memory is not cleared (i.e., set to
all zeroes).
void free(void *ptr) : free() frees the memory
space pointed to by ptr ,
which must have been returned by a previous call to malloc() .
Otherwise, or if free(ptr) has already been called before,
undefined behaviour occurs. If ptr is NULL , no operation is performed.
For simplicity, your implementations of Mem_Alloc(int size) and
Mem_Free(void *ptr) should basically follow what
malloc() and
free() do; see below for details.
You will also provide two supporting functions: Mem_Available()
and Mem_Dump() , described below.
Program Specifications
For this project, you will be implementing several different routines as
part of shared libraries. Note that you will not be writing a main() routine
for the code that you handin (but you should implement one for your own
testing). We have provided the prototypes for these functions in the file
mem.h (which is available at ~cs537-1/public/mem.h); you should
include this header file in your code to ensure that you are adhering to the
specification exactly. You should not change mem.h in any way! We now
define each of these routines more precisely.
- int Mem_Init(int sizeOfRegion):
Mem_Init() is
called one time by a process using your routines. sizeOfRegion is the number
of bytes that you should request from the OS using mmap() .
Note that you may need to round up this amount so that you request memory in
units of the page size (see the man pages for getpagesize() ).
Because of rounding up, you may request more memory than
sizeOfRegion : you may use all of this memory for allocating memory
to the user. Note also that you need to use this allocated memory for your own
data structures as well; that is, your infrastructure for tracking the mapping
from addresses to memory objects has to be placed in this region as well. You
are not allowed to malloc() , or any other related function,
in any of your routines! Similarly, you should not allocate global
arrays. However, you may allocate a few global variables (e.g., a pointer to
the head of your free list.)
Return 0 on a success (when call to mmap is successful).
Otherwise, return -1. Cases where Mem_Init() should return a
failure: Mem_Init() is called more than once; sizeOfRegion is less
than or equal to 0.
- void *Mem_Alloc(int size):
Mem_Alloc() is similar to the library
function malloc() . Mem_Alloc() takes as input the size
in bytes of the object to be allocated and returns a pointer to the start of
that object. The function returns NULL if there is not enough contiguous free
space within the memory (this may be more than sizeOfRegion if it is not a
multiple of the page size) allocated by Mem_Init() to satisfy this request.
For performance reasons, Mem_Alloc() should return 8-byte aligned chunks of
memory. For example if a user allocates 1 byte of memory, your
Mem_Alloc()
implementation should return 8 bytes of memory so that the next free block
will be 8-byte alligned too. To figure out whether you return 8-byte aligned
pointers, you could print the pointer this way printf("%p", ptr) . The
last digit should be a multiple of 8 (i.e. 0 or 8).
- int Mem_Free(void *ptr):
Mem_Free() frees the memory
object that ptr
points to. Just like with the standard free() , if ptr is NULL, then no
operation is performed . The function returns 0 on success, and -1
otherwise. Return -1 if the ptr is invalid. The ptr is invalid if it is NULL or
not a value returned by Mem_Alloc() . For example, if
Mem_Alloc() returns pointers to address 0 and 16, then calling
Mem_Free() with 8 should return -1.
Coalescing: Mem_Free () should make sure to coalesce free space.
Coalescing rejoins neighboring freed blocks into one bigger free chunk, thus
ensuring that big chunks remain free for subsequent calls to
Mem_Alloc () .
- int Mem_Available(): This should print out the number of bytes that
can be allocated in the future by calls to
Mem_Alloc() . Note that
this should not include space used to store headers, bitmaps, etc. Note that
Mem_Available() returns the total amount of usable space, not the
largest contiguous space. If Mem_Alloc() was called immediately after Mem_Init() with the result of
Mem_Available() , the call should succeed.
- void Mem_Dump(): This is just a debugging routine for your own
use. Have it print the regions of free memory to the screen.
You must provide these routines in a shared library.
Placing the routines in a shared library instead of a simple
object file makes it easier for other programmers to link with your
code. There are further advantages to shared (dynamic) libraries over static
libraries. When you link with a static library, the code for the entire
library is merged with your object code to create your executable; if you link
to many static libraries, your executable will be enormous. However, when you
link to a shared library, the library's code is not merged with your program's
object code; instead, a small amount of stub code is inserted into your object
code and the stub code finds and invokes the library code when you execute the
program. Therefore, shared libraries have two advantages: they lead to smaller
executables and they enable users to use the most recent version of the
library at run-time. To create a shared library named libmem1.so , use the
following commands (assuming your library code is in a single file
"mem.c "):
gcc -c -fpic mem.c -Wall -Werror
gcc -shared -o libmem1.so mem.o
To link with this library, you simply specify the base name of the library
with "-lmem1" and the path so that the linker can find the library "-L.".
gcc -lmem1 -L. -o myprogram mymain.c -Wall -Werror
Of course, these commands should be placed in a Makefile. Before you run
"myprogram ", you will need to set the environment variable,
LD_LIBRARY_PATH ,
so that the system can find your library at run-time. Assuming you always run
myprogram from this same directory, you can use the command:
setenv LD_LIBRARY_PATH ${LD_LIBRARY_PATH}:.
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, you simply need to
run:
setenv LD_LIBRARY_PATH .
Note that setenv is what you use in tcsh; if you are using bash, you'll
have to commands such as export .
Handing In Code
You should handin whatever files you use to implement your library, along
with a Makefile that will generate the required libraries. The Makefile should
have the all target, so that if we simply do make , we should
get all the required libraries. If your Makefile requires us to do
make my_project_name , you will fail the tests.
Workloads
Performance can often be improved drastically if the implementation is tailored
to the workload. In this project, you will have a chance to understand this
first-hand!
Your library will be tested with three workloads. You should submit
the code for three libraries - libmem1.so , libmem2.so , and
libmem3.so .
Workload 1: All calls to Mem_Alloc() will have
size as 16 bytes. Mem_Alloc() can return NULL
otherwise.
Workload 2: All calls to Mem_Alloc() will have
size as one among 16, 80, and 256 bytes. Mem_Alloc()
can return NULL otherwise.
Workload 3: Calls to Mem_Alloc() may have
any size .
Unix Hints
In this project, you will use mmap to map zero'd pages (i.e., allocate new
pages) into the address space of the calling process. Note there are a number
of different ways that you can call mmap to achieve this same goal; we give
one example here:
// open the /dev/zero device
int fd = open("/dev/zero", O_RDWR);
// sizeOfRegion (in bytes) needs to be evenly divisible by the page size
void *ptr = mmap(NULL, sizeOfRegion, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
if (ptr == MAP_FAILED) { perror("mmap"); exit(1); }
// close the device (don't worry, mapping should be unaffected)
close(fd);
return 0;
Reading
Chapter 16 from
the free operating systems book.
Allocation Bitmap
Bitwise Operations
Note
If you use a header for each allocated block, the maximum size of such a
header is 32 bytes.
Extra Credit
For exta credit, you should make your libraries work with multiple threads. In
the tests, if we instantiate multiple threads that call
Mem_Alloc() and Mem_Free() concurrently, the library
should still work correctly. Note that Mem_Init() will still be
called only once.
Grading
Your implementation will be graded on functionality. Each library will have
different tests. In particular, we will be testing things like:
- Allocating memory correctly - suppose you
Mem_Init() 1024 bytes, you should be able to use much more of
this for allocating memory in Workload 1, rather than in Workload 3 (can
you figure out why?)
- Freeing allocated memory successfully
- Coalescing memory successfully - calls to
Mem_Alloc () should succeed if enough memory has
been freed. For example, if we start with 1024 bytes, allocate 512 bytes in
units of 16 bytes, and then free all of them, we should be able to
reallocate the 512 bytes.
Test Information
For each Workload library, we will be testing that a user is able to allocate a
certain number of bytes. This should constrain the size of the headers in each
library. In these tests, we don't fragment memory, so the user should be able
to ideally use all of the space.
If we Mem_Init(4096) , then the user should be able to
allocate:
- 4032 bytes for Workload 1.
- 3840 bytes for Workload 2.
- 1344 bytes for Workload 3.
If we Mem_Init(1024*1024) , then the user should be able to
allocate:
- 983040 bytes for Workload 1.
- 786432 bytes for Workload 2.
- 349504 bytes for Workload 3.
To run the tests, execute:
python ~cs537-2/testing/p3a/MemTest.pyc dir
where dir is the directory containing your code. To help you
debug, we are releasing the C code containing the actual tests. To access
the tests, check in ~cs537-2/testing/p3a/3aTests/ . There is a
folder containing tests for each workload. For example, bucket_wl1
contains the tests for Workload 1.
Contest!
We will be holding a contest among students of each section. The contest will
proceed as follows. To participate, students need to handin the code for
libcontest1.so and libcontest2.so .
The tests for the contest are available at
/u/c/s/cs537-2/testing/p3a/3aTests/contest .
Time. We will link your libcontest1.so with
time.c . The program has to run without triggering any assertions.
We will measure the time taken for the program to run. This will be measured as
T .
Space. We will link your libcontest2.so with
space.c . The program has to run without triggering any assertions.
The code will output the total number of bytes successfully allocated. This
will be measured as N .
There are three winners for time in each section: the people who get
the least three values of T .
There are three winners for space in each section: the people who get
the highest three values of N .
Two extra rules concerning winners:
- A student may win in only one of the contests
- Only one grad student can win in each contest - the other two winners
must be undergrad students
Prizes will be CS 537 T-Shirts to show off your hard-won glory! Stay tuned for more
details about the T-Shirts!
|