Memory management

This session is dedicated to the memory management performed by an Operating System.

You don't have to submit source files or reports for this sessions. For this session, you will need to log into a PC running Linux. If you are at Eurecom, simply log on a PC of rooms 53 or 54.

I. Basics of Memory Management

1. Open the slides Memory management


2. Watch the video on the fundamental aspects


3. Can you explain what is the dual mode of a processor and what is its goal? If not, you should refer again to the introduction session


4. Allocation algorithms. In average, "Best fit" takes more time to find a slot than "First fit". Is is true or false?


5. From a global point of view, why is "Best fit" less efficient than "First fit"
(Help me!) Best fit tends to create a lot of fragmentation in memory, thus leading to create very small chunks of memory. Thus, when a large chunk of memory is requested by a process, Best fit tends to fail to return a chunk when first fit will succeed.

II. Main mechanisms

1. Open the slides Memory management, main mechanisms


2. Watch the video on main mechanisms


3. Data Sharing with Segmentation. Fill the two tables. You should notice how a segment can be shared between two processes.


4. MMU. Explain with your own words what are the main interests of a MMU for an Operating System.
(Help me!) I see two main interests for MMU. 1) Making it possible to have a virtual address space within a processor thus facilitating the compilation and execution of processes (static addresses can be determined at compilation time). This first point includes also the translation from virtual addresses to physical adresses in an efficent way (hardware support). 2) The protection of memory between processes, with a trap mechnism to inform the processor when an adress is invalid, thus offering a way for OS to detect memory addressing problems and to support swapping.



5. Use of Memory in Programs. The code provided in this slide has an error (well, in fact a warning): you should identify this error and correct it.
(Help me!) Put this code in a small program and compile it.

III. Memory management in Windows and in Linux

1. Open the slides Memory management, Windows and Linux section


2. Watch the video on Windows and Linux

IV. Memory statistics

1. Several utilities / commands make it possible to investigate the usage of memory in your system, e.g., free, vmstat, and top. Use manual pages of those commands to print information on the memory usage of your PC. Let's do it with free:

$ free

(Experiment each command with different options)

(Help me!) One of my favourite command is:
$free -lh



2. Let's now investigate the usage of memory per process. Information on a process whose process id is pid is stored in /proc/pid/status. Get the pid of your web browser (e.g., firefox), and read its corresponding status file. Can you know how much memory is really used? What other information can you learn about your process? You may need to read some documentation on the various memory areas. First, you may use the manual pages:

$ man proc

There are also a few web pages that may help you: VmRSS vs. RSS, Virtual memory vs. resident memory, and What is overcommit.
(Help me!) For the first question, do (with the pid of your process):
$ more /proc/pid/status
You can also get more information with e.g.:
$ more /proc/pid/statm
And figure out what the results mean (e.g. with the provided links)

V. Using buffers

Now, you will practice with the use of buffer overflows to modify the memory of a running program.

1. First, save the source code, decompress it, open the buf.c file, and understand the main() function. At that step, you do not need to understand the rot13() function. Let's compile the program into buf:

$ make overflow

You may get warnings, but we don't care about them at first


Now, see in which executable format your program was compiled to:

$ file buf



2. Let's now see whether the password can be seen in the executable file. Let's analyze buf:

$ hexdump -C buf

You should see a dump in both hexadecimal and string format of the binary executable buf file. Can you find the password in that file? Of course, it is in clear text in the buf.c file, but try to locate it as well in the binary file. Another way to do is to use the string command: it displays all the "readable" strings that the binary file contains.

$ strings buf



3. Let's now execute the file:

$ ./buf

It should prompt you for the password. Enter the right password, and see what you obtain.

4. Let's execute buf, but let's enter a short and wrong password, e.g., "iloveos": you should not obtain the secret value.


5. Let's finally execute buf, and let's enter a long and wrong password, e.g., "eurecomissuchaniceplacetostudyos". Do you obtain the secret? Do you have an idea why you can obtain this? If you don't have any idea on the problem, don't worry: what you are going to do in the next questions is to precisely explain you what happens.


6. We're now going to closely investigate why we can retrieve the secret when entering a wrong password. We're going to use a debugguer named gdb (documentation) to understand this tricky memory issue:

First, we need to recompile buf with the debug symbols:

$ make overflow-debug

Then, we can start to debug buf:

$ gdb buf

gdb offers many interesting functionalities, in particular, putting breakpoints in the code (break), doing step-by-step simulation (n). Whenever you need help, just type help in gdb. Type quit to exit gdb.
Once in gdb, we first put a breakpoint on line "x" (find that number!), just before the "if(pass)" test (x being the line number):

(gdb) break x

Ok, now, let's run the application, and let's enter the right password:

(gdb) run

When the execution stops at the breakpoint, you can investigate the value of the "myToken" variable:

(gdb) p myToken

Another way to do is to print all variable local to the current function (i.e., main()). First, let's verify that main() is the function under execution:

(gdb) bt 

Then, let's display the local variables:

(gdb) info locals

Do the same manipulation - using gdb - with the right password, the short and wrong password, and the long and wrong password, and understand/explain what you obtain.



7. Now, enter a very long password (e.g., two times the former long password): what do you observe? Why do you obtain this "segmentation fault"?

At that step, you should have understood that variables of the stack of the main functions are smashed by the string you enter, whenever that one is longer than 15 characters. The longer the entered string, the more damage is done to the stack elements. You may want now to read more explanations about stack smashing, and in particular, have a look at the provided figures. Before going to next steps, closely understand the reason why you get a segmentation fault: you should be able to explain this with your own words.



8. Now, let's compile the same source code differently (read the Makefile first):

$ make nooverflow

Retest the long and wrong password with the newly generated executable file (nobuf).

$ ./nobuf

(Help me!) You should get something like:
*** stack smashing detected ***



9. Now, we would like to avoid the wrong password issue even when compiling buf.c with the "-fno-stack-protector" option. Modify the way variables are declared/used, compile, and test.


10. Resolve the stack based overflow problem. To achieve that goal, re-implement the program by replacing gets with another method. Compile with the "-fno-stack-protector" option and test.


11. The password can be seen in clear format in the source file. Reuse the substitution cipher rot13() function to hide it. rot13 does not offer a very good protection. It was developed in ancient Rome in order to hide clear texts in messages. Test with hexdump that the password is no longer in clear text in the executable binary file.


12. Even with a rot13, the password can still be retrieved at execution with gdb. Use gdb to retrieve the password in clear format when executing buf. Actually, the usual secure way to handle passwords in programs is to rely on hashed passwords, and definitely not on rot13 encoding...

Next exercices are to go futher on memory management. Have fun with them!

VI. Process admittance and execution (Bonus)

1. The execution of a process started with execve() may fail for several reasons. Find out a few reasons for this failure using manual pages.


2. Make a program to illustrate one of these failures.

VII. Swapping (Super bonus)

1. Recall reasons for which a process may be swapped out.


2. Make your Linux system swap. To do so, make your own program, that progressively allocates memory. With commands you've experimented before, investigate what happens when running your program. What is the maximum amount of memory you manage to allocate with your program? What happens when the main memory is full? What happens when the swap is full?