CS450 -PA3
Jenifer Rodriguez Delgado A20398938
Yousef Suleiman A20463895
A very simple program “part1.c” was created with the purpose of allocating some memory and
not freeing it. This program calls malloc() to allocate 2k bytes of memory. After calling
malloc(2000), a print statement should display with message “Memory was allocated and not
freed”. The purpose of this is to see if that line of code would be read or not.
Figure 1: part1.c program
When compiling the program, a warning popped up but to say that we did not use for any
purpose the memory that was allocated. However, the program compiled and ran normally
(a.out) without any error and printed the statement “Memory was allocated and not freed”.
Therefore, 2k bytes of memory were allocated successfully and even though there was a leak, the
program did not stop.
Figure 2: compile and run of part1.c
When using gdb (the GNU Project debugger) command, we are still not able to catch the leak
problem. That is because gdb does not have features to help us since it only checks the stack.
And we would need a debugger that would check for heap and memory leaks. The command
“gdb ./a.out” was typed in the shell. When the “run” command is typed, part1.c program runs
correctly and exits without issue. I exited gdb by entering ctrl+z. The figure below represents
everything that happened when using gdb.
Figure 3: Using gdb
“Valgrind” was originally designed to be a free memory debugging tool for Linux on x86.
When using the “valgrind –leak-check=yes ./part1” command in the shell, a report summary was
displayed. First, we can see that in “HEAP SUMMARY”, there were 2 allocs but only 1 free.
Then says “2,000 bytes in 1 blocks are definitely lost in loss record 1 of 1”. It also mentions the
address of the malloc. Also, right below that we can see a “LEAK SUMMARY”, that states that
2,000 bytes in 1 block were definitely lost.
In conclusion, using “valgrind” is very useful for memory leaks and detected the leak in part1.c
The figure below shows the display report using valgrind.
Figure 4: Using valgrind
Test cases
Test#1 – test1.c program was created. A very simple program that allocates space for an array of
10 ints (each int has the value of position+1) then frees the array. “test1.out” was created.
Output should be: No leaks or errors when running valgrind and array displayed from 1-10.
Result was as expected. No leaks
Test#2 Uninitialized value- test2.c was created. Same program as test1.c but only 1 int and it is
uninitialized. Since Valgrind also reports errors of uninitialized values. “test2.out” was created.
Output should be: Error display regarding uninitialized value. There should not be a leak
problem since we are freeing the array.
Result was as expected. We can successfully see how we get errors regarding the uninitialized
int, but no leak issues.
Test#3 writing/reading after freeing- test3.c was created. This program allocates memory for an
array of ints size 5 (starting at 0), the program tries to write “9” at position array[4] once it has
been freed. We should see an error display of Invalid Write/Read. Should not show errors for
leak.
As expected, valgrind’s summary shows Invalid Write and Read. No leakage problems. We can
still see the array printed because the data was saved.
Test#4-r/w out of boundaries. test4.c was created. This program tries to write “133” in array[5],
which is passed to the end of the malloc() block. We should see an Invalid Write/Read error
similar as test case#3.
As expected, we see in the report an invalid write and read size 4 (int size) and the address at
where it was, which is where we tried writing outside of limits.
Test#5- freeing twice. test.5.c was created. This program frees twice. We should see an error
when running valgrind about invalid free.
As expected, we can see the invalid free error and also in the Heap Summary 6 allocs and 11
frees.
CS450 -PA3
Jenifer Rodriguez Delgado A20398938
Yousef Suleiman A20463895
Design of GetSharedPage()
GetSharedPage() takes an integer key (any integer other than 0) and an integer count
(greater or equal to 1) signifying how many shared pages the user process is requesting under
that key. Any other process using a subset of those shared pages under the same key will be
writing onto the same physical pages in memory.
The key was designed to have an integer value to make simple and quick comparisons. It is not
allowed to have a value of 0 as 0 is used as a sentinel value by a function called
get_proc_key() that returns 0 if it can’t find a key associated with a process. This will be
explained more in depth later in this document.
The design of GetSharedPage() was made possible by keeping track of metadata about the
physical pages that are shared as well as metadata about the address spaces of the processes
that can call GetSharedPage().
The metadata about the shared pages themselves were kept in an array of 32 struct
shared_page called all_shared_pages. The struct shared_page holds metadata
about a single shared page. This includes the page’s key, its page_number (incase this page
belongs to a set of pages under a specific key when a user requests more than one page), the
physical address of the page in memory, an array of proc’s sharing that page, and their
corresponding virtual addresses of the page in their own address space.
The metadata about the address spaces of the processes that call GetSharedPage() are
stored in a bitmap sh_bit_map within each struct proc (proc.h) with 0s to represent
free pages and 1 to represent otherwise.
Because we are using arrays to save metadata, the number of max shared pages and max
processes sharing a page are defined. It was chosen to use arrays as xv6 lacks a malloc-like
allocator so it is difficult to use data structures that require dynamic allocation.
GetSharedPage() uses 2 helper functions to get the job done: where_does_fit() and
find_shared_page().
After checking if the parameters passed to it are valid, GetSharedPage()calls
where_does_fit() and stores its return. Function where_does_fit() takes a count of
requested pages, gets the bitmap sh_bit_map of the calling process, and looks for a position
that can fit the number of pages specified by count then returns it. If no position is found that
can fit the requested count, -1 is returned.
GetSharedPage() then makes calls to find_shared_page() which takes a key,
page_number, and position to put the page in sh_bit_map. In short, function
find_shared_page() calls kalloc() if needed, updates the metadata, and maps the
shared page to the calling process’s pgdir. However, find_shared_page() only does the
job for a single page. If the user requests more than one page, GetSharedPage() uses a for
loop to call find_shared_page() multiple times.
To explain what find_shared_page() is doing, it takes the given key and page_number
used to uniquely identify every physical shared page, then walks through the array
all_shared_pages to find a shared page with matching key and page_number. If found,
the calling process is added to the array of processes sharing the page in
all_shared_pages, bitmap sh_bit_map is updated at the specified position, then uses
mappages in vm.c to put the page in the pgdir of the calling proc by passing the
virtual_address (computed through sh_bit_map and macros KERNBASE and PGSIZE)
and the physical address already stored in all_shared_pages since the page already
exists.
If an existing page with the key and page_number is not found, a new page is allocated
using kalloc(). The page is zeroed out with memset() and similar process occurs as before
where the calling process is added to the array of processes sharing the page in
all_shared_pages (along with the new key, page_number, and physical address),
sh_bit_map is updated, and mappages is called with the respective parameters.
● Note: because mappages is static, a separate wrapper function getMappages was
used to access it
If anything fails such as kalloc() or mappages() returning -1 or too many processes sharing
the page, then find_shared_page() returns -1. If successful, it returns the
virtual_address of the page.
After calling find_shared_page() in a for loop, GetSharedPage() returns the
virtual_address from the last call to find_shared_page(). (it breaks its for loop and
returns -1 if find_shared_page() returns -1)
Design of FreeSharedPage()
FreeSharedPage() takes an integer key and returns the number of pages removed from the
address space of the user process if successful and -1 if not.
The design of FreeSharedPage() was made possible by again using 2 helper functions:
get_num_sh_procs() and remove_shared_page().
After checking for valid parameters, FreeSharedPage() begins by calling and saving the
return of get_num_sh_procs() which takes a key and returns the number of pages that the
calling process has under that key. FreeSharedPage() then calls
remove_shared_page() that many times in a for loop. Function remove_shared_page()
takes a key and page_number to remove the specified page from user address space and
possibly kfree() the physical page if this was the last process sharing it.
Function remove_shared_page() begins by looking in all_shared_pages for a
corresponding key and page_number. If found, the calling process is looked for in the array of
process sharing the page and is removed, its corresponding virtual address is also removed,
and the page is unmapped from the process’s pgdir by using walkpgdir to get the pte and
set it to 0. Lastly, the corresponding bit in bitmap sh_bit_map is unset.
● Note: again, because walkpgdir is static, a separate wrapper function
getWalkpgdir was used to access it
Function remove_shared_page() then calls its own helper function zero_procs() which
returns 0 if the calling process appears in all_shared_pages at least once and 1 otherwise.
If zero_procs() returns 1, remove_shared_page() uses kfree() on the physical page,
Finally the physical address of the page (previously used to possibly kfree) is set to 0 in
all_shared_pages.
Function remove_shared_page() returns -1 if the key is not found or the key does not
belong to the calling process. If that’s the case, FreeSharedPage() breaks its for loop and
also returns-1.
Side note:
Exit() in proc.c was modified to do something similar to FreeSharedPage() where it
takes all the keys associated with the exiting process using a function get_proc_key() which
returns the first key it finds associated with the calling process and 0 if no key is found. Exit()
makes calls to remove_shared_page() until get_proc_key() returns 0, freeing all the
shared pages of the exiting process.
● Note: 0 was used as a sentinel value by get_proc_key() so if a process had a key
with the value 0, it would cause complications when freeing at exit(). For this reason,
key was designed to have a value other than 0.
Changes were made in the following:
● sysproc.c
○ contains the actual body of GetSharedPage() and FreeSharedPage()
● types.h
○ makes a typedef for int key_int
● defs.h
○ defined and declared struct shared_page and array of struct shared_page
called all_shared_pages
■ struct shared_page contains metadata on a particular shared page
such as an integer key, the integer page_number under a certain key,
the physical address phy_add, and an array of struct proc*
procs_sh_page, and an array of int virtual addresses
vir_add_of_page
○ declared init_shared_page(), find_shared_page(),
where_does_fit(), remove_shared_page(), zero_procs(),
get_num_sh_procs(), and get_proc_key()
■ These are all defined in our own . c file called sharepage.c
● vm.c
○ in deallocuvm() don’t kfree a page if its phy_add is still in the
all_shared_pages array (meaning some process is still using the shared
page). This is done by searching all_shared_pages for phy_add equal to
pa in the function
○ in copyuvm() the parent’s shared address space was completely copied and
mapped over to the child’s using the beginning and end of the shared memory
uint sh_mem_start = KERNBASE – PGSIZE;
uint sh_mem_end = KERNBASE – MAXSHPAGES * PGSIZE;
Then walking pgdir to make sure the page is there and using mappages() to
map to the child
○ also added getMappages() and getWalkpgdir() to easily access
mappages()and walkpgdir() static functions in sharepage.c
● proc.h
○ added bitmap of shared pages sh_bit_map to struct proc
● proc.c
○ userinit() initializes all_shared_pages_array through
init_shared_page() by zeroing everything out as well as using memset()
to zero out the bitmap sh_bit_map
○ change fork() to copy the bitmap sh_bit_map and all_shared_pages
metadata
○ change exit() to make calls to get_proc_key() and
remove_shared_page() to remove shared pages from exiting processes
CS450 -PA3
Jenifer Rodriguez Delgado A20398938
Yousef Suleiman A20463895
Test Data Explanation
shpg1test & shpg2test
● Process A requests 1 shared page under key 111 and writes “CS450 is very easy!\0”
● Process A forks B who execs shpg2test
● In shpg2test, B requests the same shared page under key 111 and overwrites it with “CS450 is
very hard!\0”
● Process A reaps B and reads what B has overwritten the page with
Figure 1 demonstrates that a single page is properly shared between two user processes.
shpg3test
● First process A requests 5 shared pages with key 500 and gets pages with PFNs of a, b, c, d, e
● Process A writes on all 5 pages using 5120 integers
○ each integer is 4 bytes so a 4096 byte page can hold 1024 integers
○ 5 pages can hold 5120 integers
● Process A forks process B who still has access to the shared pages of PFNs a, b, c, d, e (inherited by
A)
● Process B reads from these pages
● Process B then requests 3 mores shared pages with the same key and thus gets back pages with
PFNS c, d, e
○ B’s virtual address space has 8 shared pages with PFNs of a, b, c, d, e, c, d, e (the virtual pages
with the same PFNs are synced)
● Process B then writes on these 3 pages, multiplying the integer values by 2
● Process A reaps process B then reads its 5 shared pages (PFNS a, b, c, d, e) with 3 of them (PFNS c,
d, e) having values overwritten by process B
Figure 2 demonstrates that a process can request multiple shared pages and write across all of them
using the returned virtual address. It also shows that a child inherits its parent process’s shared
pages. By having the child also request a subset of the pages under the same key, writing in them,
then having the parent read those pages shows that multiple pages can be properly shared.
shpg4test & shpg5test
A “silly loop”
● Process A requests 1 shared page under key 313, writes integer value 20 in it
● A forks B who exec’s shpg5test
● In shpg2test, B requests the same shared page under key 313 then decrements the integer value,
prints, and frees its shared page
● B execs shpg2test again and loops until the integer value is 0
● A reaps B and prints the 0 integer value
● To prove the pages are being freed by FreeSharedPage(), the original integer value 20 is greater
than 16
● exec() does not free the page so it does not remove the procs from procs_sh_page in
all_shared_pages
● Thus, if they were not being freed, we’d get an error returned as such:
Figure 3 demonstrates that when calling FreeSharedPage(), the process is removed from the
array holding the list of processes accessing the page, but kfree() is not called on the physical until
no other process is accessing it.
shpg6test
● This test makes sure it is mapping the pages in the right spots in the address space
● The process requests 1 page under key 111 so sh_bit_map looks as ‘A 0 0 0 0 …’ where ‘A’ is the 1
bit belonging to key 111. Then it writes 111 across the page.
● Next, it requests 1 more page under key 222 so sh_bit_map looks as ‘A B 0 0 0 …’ where ‘B’ is the
1 bit belonging to key 222. Then it writes 222 across the page.
● Next, it calls FreeSharedPage(111) so sh_bit_map looks as ‘0 B 0 0 0 …’
● Lastly, it requests 2 more pages under key 333 so sh_bit_map looks as ‘0 B C C 0 …’ where ‘C’ are
the bits belonging to key 333. Then it writes 333 across the page.
● To prove they are placed correctly and not as ‘C B C 0 0 …’ the process reads from the pages using
pointer arithmetic
Figure 4 demonstrates that when multiple pages are being requested, they are placed consecutively
in the user address space such that they can be written on using the return virtual address.