Project04 Implementing mmap() in xv6

Deliverables due Wed May 7 by 6:25pm in your project04 GitHub repo

You will demo your working mmaptest program in lab section on May 7.

• A copy of xv6 with your implementation of mmap() functionality
• Your source code should conform to xv6 formatting conventions.
• Your Project04 repo should not have any extraneous files or build artifacts
• You will demo your solution in Lab Section on Wed May 7.

Overview

Memory mapping (mmap) is a powerful mechanism in modern operating systems that allows processes to map files or devices into their address space. It’s particularly useful for allowing processes to share memory. In this project, you will implement a simplified version of mmap() in xv6 that focuses on providing shared memory functionality between processes.

The primary goal of your implementation will be to allow multiple processes to share memory pages, enabling direct inter-process communication. This is a fundamental feature of modern operating systems, and implementing it will deepen your understanding of virtual memory, page tables, and process management in xv6.

Page Tables in xv6

Before diving into the implementation, it’s important to understand how page tables work in xv6 running on RISC-V.

Virtual memory in xv6 uses a three-level page table structure following the RISC-V Sv39 standard:

63   39 38           30 29           21 20           12 11            0
+-------+---------------+---------------+---------------+---------------+
| Unused|   L2 Index    |   L1 Index    |   L0 Index    |    Offset     |
| (must |   (9 bits)    |   (9 bits)    |   (9 bits)    |   (12 bits)   |
| be 0) |               |               |               |               |
+-------+---------------+---------------+---------------+---------------+

Each page table contains 512 entries (PTEs), and each PTE is 64 bits that contains both the physical address and permission bits:

63           54 53        28 27        19 18        10 9   8 7 6 5 4 3 2 1 0
+---------------+------------+------------+------------+-----+-+-+-+-+-+-+-+-+
|    Reserved   | PPN[2]     | PPN[1]     | PPN[0]     | RSW |D|A|G|U|X|W|R|V|
+---------------+------------+------------+------------+-----+-+-+-+-+-+-+-+-+

Where:

• V: Valid bit
• R: Read permission
• W: Write permission
• X: Execute permission
• U: User mode access
• PPN: Physical Page Number

For our mmap() implementation, we’ll need to create mappings that point to the same physical page from multiple processes’ page tables, effectively creating shared memory.

Implementation Approach

Your goal is to modify the xv6 kernel to support a simplified version of mmap() for shared memory. For this project, we’ll implement:

1. A restricted mapping area above the heap and below the stack
2. Support for a single 4KB shared memory page
3. Reference counting to track shared pages
4. Cleanup on process exit and explicit unmapping

You will need to implement two new system calls:

• mmap(): Allocate and map a shared memory page
• munmap(uint64 addr): Unmap a previously mapped memory page

These system calls should handle memory sharing between parent and child processes, reference counting to manage the shared page’s lifecycle, and proper cleanup when processes exit.

System Call Specifications

uint64 mmap(void)

Purpose:
Requests allocation and mapping of a shared memory page.

Parameters:
None - this simplified implementation doesn’t require parameters.

Return Value:

• Virtual address of the mapped page on success (always at SHMEM_REGION)
• 0 on failure

Behavior:

• If this is the first process to call mmap(), a physical page should be allocated and mapped at SHMEM_REGION
• If a shared page already exists, increment its reference count and map it into the calling process’s address space
• The page should be mapped with read/write permissions for user mode
• If mapping fails, any allocated resources should be freed

int munmap(uint64 addr)

Purpose:
Unmaps a previously mapped shared memory page.

Parameters:

• addr: The virtual address of the shared memory mapping to remove

Return Value:

• 0 on success
• -1 on failure

Error Conditions:

• Returns -1 if the address is not a valid mapped shared memory address
• Returns -1 if the page at the specified address is not mapped

Behavior:

• Removes the mapping from the process’s address space
• Decrements the reference count for the shared page
• If the reference count reaches zero, frees the physical page
• Updates the page table to remove the mapping

Implementation Requirements

Key Data Structures

You will need to implement a global structure to track the shared memory page:

// Structure to track our single shared memory page
struct {
  uint64 pa;              // Physical address of the shared page
  int refcount;           // Reference count
  struct spinlock lock;   // Lock to protect access
  int allocated;          // Whether the page is allocated
} shmem_page;

// Define a specific region for shared memory
#define SHMEM_REGION 0x4000000  // 64MB mark

Files to Modify

1. kernel/defs.h: Add function prototypes for shared memory operations
2. kernel/syscall.h: Add new syscall numbers for mmap and munmap
3. kernel/syscall.c: Register the new syscalls in the syscall table
4. kernel/vm.c: Implement shared page memory management functions
5. kernel/sysproc.c: Implement syscall handlers
6. kernel/main.c: Initialize the shared memory system
7. user/user.h: Add user-side declarations for the syscalls
8. user/usys.pl: Add syscall entries to generate user stubs
9. Makefile: Add mmaptest to the build process

Required Modifications

1. kernel/defs.h

Add function prototypes for shared memory management:

// Add to kernel/defs.h
void            init_shmem(void);
uint64          sys_mmap(void);
int             sys_munmap(void);
uint64          mmap(void);
int             munmap(uint64 va);

2. kernel/syscall.h

Add syscall numbers for the new system calls:

// Add to kernel/syscall.h
#define SYS_mmap    23  // Use next available syscall number
#define SYS_munmap  24

3. kernel/syscall.c

Register the new syscalls in the syscall table:

// Add to kernel/syscall.c
extern uint64 sys_mmap(void);
extern uint64 sys_munmap(void);

// Add to syscalls[] array
[SYS_mmap]    sys_mmap,
[SYS_munmap]  sys_munmap,

4. kernel/vm.c

Implement the shared memory tracking structure and core functionality:

1. Define the shmem_page structure to track the shared page
2. Implement init_shmem() to initialize the shared memory system and its lock
3. Implement the core mmap() function with these responsibilities:
   • Acquire a lock to protect shared memory operations
   • Check if this is the first allocation request for the shared page
   • If first request, allocate a physical page with kalloc() and clear it
   • If page already exists, reuse it and increment its reference count
   • Map the physical page into the process’s address space at SHMEM_REGION

   • Set appropriate page permissions (PTE_R

     PTE_W

     PTE_U)

   • Handle error cases by decrementing the reference count and freeing resources if needed
   • Return the virtual address of the mapped shared memory region
4. Implement the munmap() function with these responsibilities:
   • Validate that the address is the shared memory region address
   • Use the walk() function to find the page table entry (PTE) for the given address
   • Check if the page is valid and mapped
   • Clear the PTE to remove the mapping
   • Acquire the lock to safely modify the reference count
   • Decrement the reference count for the shared page
   • If reference count reaches zero, free the physical page with kfree()
   • Release the lock and return success/failure code
5. Modify the uvmcopy() function (used during fork) to handle shared memory:
   • When copying a process’s address space to a child process during fork
   • Detect when the address being copied corresponds to SHMEM_REGION
   • Instead of creating a new copy of the physical page, map the same physical page
   • Use mappages() to add the shared page to the child’s page table with the same permissions
   • Increment the reference count to track the new mapping
   • This ensures both parent and child share the same physical memory
6. Modify the uvmunmap() function (used during process cleanup) to handle shared memory:
   • When unmapping process memory during process termination or explicit unmapping
   • Detect when the address being unmapped corresponds to SHMEM_REGION
   • For the shared page, decrement its reference count instead of immediately freeing
   • Only free the physical page when the reference count reaches zero
   • Continue normal operation for non-shared pages

5. kernel/sysproc.c

Implement system call handlers:

// Add to kernel/sysproc.c
uint64
sys_mmap(void)
{
  return mmap();
}

uint64
sys_munmap(void)
{
  uint64 va;
  
  if(argaddr(0, &va) < 0)
    return -1;
    
  return munmap(va);
}

6. kernel/main.c

Initialize the shared memory system:

// Add to kernel/main.c in main() function
init_shmem();

7. user/user.h

Add user-side declarations:

// Add to user/user.h
uint64 mmap(void);
int munmap(uint64);

8. user/usys.pl

Add syscall entries:

# Add to user/usys.pl
entry("mmap");
entry("munmap");

9. Makefile

Add mmaptest to the build:

UPROGS=\
  ...
  $U/_mmaptest\

Memory Mapping Test Program

The following test program will verify your mmap implementation:

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int
main(int argc, char *argv[])
{
  int pid;
  uint64 shared_addr;

  printf("Testing mmap shared memory...\n");

  // Map shared memory
  shared_addr = mmap();
  if(shared_addr == 0){
    printf("mmap failed\n");
    exit(1);
  }

  printf("Mapped shared memory at 0x%p\n", (void*)shared_addr);

  // Write to shared memory
  int *shared_data = (int*)shared_addr;
  *shared_data = 42;
  printf("Parent wrote: %d\n", *shared_data);

  // Fork a child process
  pid = fork();
  if(pid < 0){
    printf("fork failed\n");
    exit(1);
  }

  if(pid == 0){
    // Child process
    printf("Child read: %d\n", *shared_data);

    // Modify the shared data
    *shared_data = 100;
    printf("Child wrote: %d\n", *shared_data);

    // Test unmapping in child
    if(munmap(shared_addr) < 0)
      printf("Child: munmap failed\n");
    else
      printf("Child: munmap succeeded\n");

    exit(0);
  } else {
    // Parent process
    wait(0);

    // Verify the child's modification is visible
    printf("Parent read after child: %d\n", *shared_data);

    // Unmap shared memory
    if(munmap(shared_addr) < 0)
      printf("Parent: munmap failed\n");
    else
      printf("Parent: munmap succeeded\n");
  }

  exit(0);
}

Expected Output

When your implementation is complete, running mmaptest should produce output like:

$ mmaptest
Testing mmap shared memory...
Mapped shared memory at 0x4000000
Parent wrote: 42
Child read: 42
Child wrote: 100
Child: munmap succeeded
Parent read after child: 100
Parent: munmap succeeded

This confirms that:

1. Shared memory can be mapped at the designated address
2. Data written by the parent can be read by the child
3. Data modified by the child is visible to the parent
4. Both processes can unmap shared memory successfully

Implementation Guidelines

1. Start by setting up the system call infrastructure before implementing the core functionality
2. When implementing mmap(), first focus on getting it working for a single process
3. Then modify fork to handle the shared page correctly
4. Implement proper reference counting to manage the shared page lifecycle
5. Finally, implement munmap() with proper cleanup
6. Test thoroughly to ensure shared memory works as expected

Remember that the goal is to implement a simplified version of mmap() focused specifically on shared memory between processes, not the full POSIX mmap() functionality.