Transcript Mem allocation background

Project 3
• Purpose: understand how memory allocators provide virtual memory to
programs.
• Write a BiBOP style simple memory allocator
–
–
–
–
–
Page size = 4K
Segregated size classes of pages
Limits external fragmentation
Can be very fast
Each page also contains a header, containing metadata about the page
• Implement basic malloc and free API in allocator.cc.
• Compile into a shared library: libmymalloc.so
Computer Science
CS377: Operating Systems
Discussion 8
, page 1
• Input:-
• Allocator will run as a layer between any program and OS.
• This layer will handle memory related system calls, and in turn request memory
from the OS using mmap.
• Input is a sequence of calls to malloc and free.
– Calls intercepted by a shim layer.
• Output:• No output
Computer Science
CS377: Operating Systems
Discussion 8
, page 2
• Implementation details:-
• allocator will allocate memory in units of pages (4K)
– Segregated by different sized: 23 to 210 bytes.
– Larger objects specially handled.
– Bibop header.
Computer Science
CS377: Operating Systems
Discussion 8
, page 3
• To allocate memory from OS, use the following code:
#include <fcntl>
#include <stdlib>
#include <sys>
int fd = open(“/dev/zero”, O_RDWR);
void * ptr = mmap (NULL, sz, PROT_READ |
PROT_WRITE, MAP_PRIVATE, fd, 0);
Computer Science
CS377: Operating Systems
Discussion 8
, page 4
• To return memory call munmap:– munmap(ptr, size);
• The BiBop header needs to be located at the beginning of a page/area that you
allocated with mmap. To do this you can use a "placement new":
bibop_ptr = new (page_ptr) BibopHeader;
• This allocates a BibopHeader at page_ptr address.
• Write allocator.cc corresponding to allocator.h
Computer Science
CS377: Operating Systems
Discussion 8
, page 5
• Allocating memory inside the allocator:
– Allocate only for the user program
– Do not call new or malloc directly or indirectly
– Do not use STL which uses heap memory
– Can use some global variables
• Make your program space efficient
– Extra or out of order calls marked as wrong
Computer Science
CS377: Operating Systems
Discussion 8
, page 6
• Choosing space to allocate:-
– When allocating a new page, please place it at the head of the list of pages
of that size. The next allocation will occur from that page.
– When a page becomes full, move it to the head of a separate list of pages
that are full.
– When a page that was full has an object freed, move it to the head of the list
of pages with space available. The next allocation will occur from that
page.
– You can chose any object inside the page to allocate.
• Using two lists is not necessary for large objects
Computer Science
CS377: Operating Systems
Discussion 8
, page 7
• Compiling:-
g++ -O2 -DNDEBUG -Wall -shared allocator.cc –o libmymalloc.so libshim.a –ldl
• Running:-
export LD_PRELOAD=./libmymalloc.so
./test
• Your allocator will run on simple programs only.
• Compiling as part of a program:g++ -Wall -g -o test allocator.cc test.cc libshim.a -ldl
Computer Science
CS377: Operating Systems
Discussion 8
, page 8
• Testing:– Some real programs: pwd, df
export LD_PRELOAD=/your/directory/goes/here/libmymalloc.so
/usr/bin/time benchmark
0.00user 0.00system 0:00.00elapsed 50%CPU (0avgtext+0avgdata
0maxresident)k
0inputs+0outputs (0major+274minor)pagefaults 0swaps
Computer Science
CS377: Operating Systems
Discussion 8
, page 9
• Performance hints:-
• Finding a BibopHeader for a previous allocation should be constant time.
• Finding a free page to allocate for any particular size should occur in constant
time.
• If your allocator is no longer using a page, it should be returned to the operating
system.
• Only open /dev/zero once.
Computer Science
CS377: Operating Systems
Discussion 8
, page 10
• Submission:-
./submit377 2 allocator.cc
• Helper files (allocator.h, libshim.a) can be found in –
/courses/cs300/cs377/cs377.f2008/project3
Computer Science
CS377: Operating Systems
Discussion 8
, page 11