Operating systems

Portail informatique

Shared memory

This lab aims to make you understand how memory is managed in an operating system and how shared memory segments are implemented.

A small interface for printf

To warm up, we invite you to deepen your knowledge of macros. The code you will write in this exercise will be useful later to hide some differences between the POSIX (Linux) and xv6 interfaces. Completing this exercise does not require xv6.

In a shm-posix.c file, define the following macro:
#define foo(a0, ...) a0 + __VA_ARGS__
In the main function of shm-posix.c, call foo(1, 2, 3) and observe the code generated by gcc -E.

Based on the previous example, define a macro named dprintf (for debug printf) in shm-posix.c that prints a message to the standard output. This macro has the same interface as printf, i.e. the number of parameters is variable (see man 3 printf). Modify the main function of your program to call dprintf("the %s command started with %d parameters\n", argv[0], argc).

in a similar way to dprintf, add a macro error having the interface of printf and printing the message on the standard error stream. Your macro should also end the process with an exit.

Test the following code by compiling with the option -Wno-error=multistatement-macros :
if(0 == 1) error("I am a camel\n"); dprintf("I am a process\n");
You may encounter a compilation error indicating a problem with the parameters passed to printf. By examining the code generated by gcc -E, you can notice that although no variadic parameter is passed, a comma remains. You can fix this by using ##__VA_ARGS__ instead of __VA_ARGS__.

Why can't you see any display?

Remember to compile with gcc -E to see the code actually compiled by gcc.

To fix the problem identified in the previous question, you must be able to regroup instructions together to form a block. You could group the dprintf and the error with curly braces, but in this case the user could omit the semicolon at the end of the statement, which could quickly make the program unreadable. To force the macro user to add a semicolon, you have two solutions. You can use a do ... while like here:
do { statement1 ; statement2 ; } while(0)

Or you can use enclose the block with braces and parentheses like here
({ statement1 ; statement2 ; })

Fix the problem identified in the previous question.

POSIX shared memory

In this exercise, you will write a program using a shared memory to synchronize two processes. Firstly, this program is executed in a POSIX environment (ie under Linux).

In the rest of the lab, use dprintf rather than printf to display information, and error to exit in case of errors.

In shm-posix.c, create a child process that prints a message before exiting. The parent must wait for the end of the child before printing a message.

Modify your program so that:
  • Before the creation of the child process:
    • The parent creates a shared memory segment of size 8192,
  • Then, after the creation of the child process:
    • The parent maps this segment into its address space at address 0x10000000 before destroying the mapping,
    • The child maps this same segment into its address space, but at the address 0x20000000 before destroying the mapping,
    • The parent destroys the shared memory segment after the child terminates.
Remember to handle errors.

You will find the following functions useful:
  • shm_open: opens or creates a shared memory segment. A use typical is
    int fd = shm_open("my-key", O_RDWR | O_CREAT, 0777);
  • ftruncate: allows to specify the size of a memory segment shared previously opened. A typical use is
    ftruncate(fd, 65536);
  • mmap: allows you to map the shared memory segment in the address space of the process (more generally, mmap allows to map any file). Typical use is:
    void* addr = (void*)0x10000000; addr = mmap(addr, 65536, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);

Initially, a shared memory segment contains only 0s. Use this property:
  • to block the parent as long as the first integer shared memory contains 0,
  • make sure that the child unlocks the father.
Carefully use the C11 interface that you saw in lesson 4 (atomic_load_explicit ...). Consider printing messages to ensure that your synchronization is correct (keep these messages which will be used in the third exercise).

Instead of using the first integer from shared memory to synchronize the parent and the child, use a global variable. Why does the synchronization not work anymore ? Restore the operation of the program using the first integer of the shared memory segment.

Similarly, block the child while the second integer is 0, and use the parent to unblock the child after the parent himself has been unblocked by the child.

Congratulations, you have just implemented a great inter-process function call! Indeed, the child is the client, sends a request to the parent who executes code, meanwhile, the child waits for the parent's response.

Implementation of a shared memory interface in xv6

The goal of this exercise is to create a new interface to manipulate the shared memory segments in xv6. At this stage, we only deal with interfaces, their implementation remains empty.

Start by getting the code for xv6:

  • git clone https://gitlab.inf.telecom-sudparis.eu/csc4508/xv6-tsp.git if you start from a new copy
  • or git checkout master if you already have a local copy of the repository

Then create a local branch to work:

git checkout -b my-shm

Copy the program shm-posix.c to shm.c in the xv6 sources and add it to the xv6 compilation chain (see the UPROGS variable from Makefile). Then, comment on the functions which take care of creating or manipulating the shared memory, then modify your program so that it compiles and runs without error with the xv6 kernel.
Since the program uses atomic functions, it is necessary to include stdatomic.h. This file is not part of xv6, but you can leave the #include "stdatomic.h" and let the compiler use the Linux version of the file.
It is likely that your program ends on a trap 14 (segmentation fault). If so, add an exit() at the end of your program.

Add the following system calls to xv6:
  • int shm_create(int size) creates a shared memory segment of size size and returns an identifier to this segment. It is the equivalent of a call to the POSIX function shm_open followed by ftruncate
  • int shm_attach(int id, void* addr) attaches the segment id at the address addr. This function is the equivalent of the POSIX mmap function.
  • int shm_detach(int id) detaches the id segment. This function is the equivalent of the POSIX munmap function.
  • int shm_destroy(int id) destroys the id segment. This function is the equivalent of the POSIX shm_unlink function.

Each of these functions should return -1 on error. Add a preliminary implementation of these functions in vm.c which prints function ??? not yet implemented and returns -1.

To add these new system calls (remember Lab #4), you must:
  • Associate a number with the various functions. It is this number that is transmitted by the process to the system during the system call. For this, we must define new constants in syscall.h.
  • On the process side, add the code to call the new system functions. It is necessary to modify:
    • user.h, which contains the signatures of the system calls,
    • usys.S, which contains the (assembler) code of these functions.
  • On the kernel side, you must add the code implementing the new system calls. It is necessary to modify:
    • vm.c to add the preliminary definitions of system calls,
    • syscall.c, which contains the table associating the system calls numbers to the implementation functions.

Uncomment the code that manipulates the shared memory segments of shm.c and adapt it to use the xv6 system calls. Check that your program has the expected behavior (calling shm_create prints "not yet implemented" and returns -1, shm.c quits with a suitable message).

Creation and attachment of a shared memory segment

In this exercise, we implement shm_create and shm_attach. To begin with, we remind you that argint(n, &v) allows you to store the nth argument passed to the system call at the address of v. To retrieve the address to which we want to attach the segment in shm_attach, you must cast to convert the integer to an address as follows:
int v; argint(1, &v); char* addr = (char*)v;

To implement these functions, we advise you to use the following data structure (to be added to vm.c) to represent the set of shared memory segments:

#define SHM_N 16 #define SHM_MAX 10 struct { struct spinlock lock; struct { char* pages[SHM_MAX]; // int npages; int nused; } shms[SHM_N]; } shms;
In this structure, shms.lock is a lock used to protect against concurrent access to the shared memory segment table. shms.shms[id] describes the shared memory segment with identifier id:
  • pages contains the virtual addresses of the shared pages (see below),
  • npages gives the number of pages of the segment (it is equal to 0 if the entry is not used, i.e. if there is no identifier segment id ),
  • nused gives the number of times the segment has been attached (this field will be used in the following exercise).
Initially, the structure is filled with zeros. Specifically, we can know that all the entries in the table are free since, for any i segment, shms.shms[i].npages is 0.
Finally, for managing memory, you should know that:
  • char* kalloc() allocates a new physical page and returns a pointer to a virtual address at which the page is mapped. This virtual address is only valid in the kernel address space.
  • int V2P(char* addr) returns the physical address of the virtual address addr if addr is an address returned by kalloc.
  • mappages(myproc()->pgdir, vaddr, PGSIZE, paddr, PTE_W|PTE_U) allows to map the physical address page paddr to the virtual address vaddr in the current process and gives the current process write permission to this page.
  • To calculate the number of memory pages to store size bytes, you can use PGROUNDUP(size)/PGSIZE.

The shm_create function must:

  • Calculate the number of memory pages to allocate
  • Find a free shm (i.e. whose npages is 0)
  • Allocate the memory pages (with kalloc) and store their address in the pages array
  • Fill the allocated pages with 0s

The shm_attach function must map the pages of the shared memory segment into memory and increment the nused reference count.

To go further: detach and destroy a shared memory segment

The aim of this exercise is to implement the shm_detach and shm_destroy functions.

To get started, in order to detach the id segment of the p process, you need to know to which address this segment had been mapped. To do this, you need to modify the proc structure in order to keep the (id, addr) associations where id is a segment identifier and addr the projection address. Edit the shm_attach function in order to store this association.

Then, to remove an association between a virtual address and a physical address in a process, there is no function in the kernel. To help you, the following code is used to mark the virtual address vaddr as invalid in the page table of the current process.

pte_t* pte = walkpgdir(myproc()->pgdir, (char*)vaddr, 0); if(!pte || !(*pte & PTE_P)) panic("unmapped page"); *pte = 0;

Finally, you should know that kfree frees a memory page.

To go even further, you can:

  • Prevent the destruction of a segment if it is still mapped in another process using the nused field.
  • Automatically detach the attached segments from a process when it ends (function exit in proc.c).