[MIT 6.S081] Lab 10: mmap

Lab 10: mmap

• Lab Guidance: https://pdos.csail.mit.edu/6.828/2020/labs/mmap.html
• Lab Code: https://github.com/peakcrosser7/xv6-labs-2020/tree/mmap

mmap (hard)

The main points of

• The implementation only considers memory mapped files mmap and munmap system call .
• mmap Parameters addr Always for 0, The virtual address of the mapping file is determined by the kernel .
• mmap Parameters flags Only consider MAP_SHARED and MAP_PRIVATE.
• mmap Use lazy allocation for memory mapping .
• Define a VMA Structure to describe the information of a piece of virtual memory . You can record with a fixed length array .

step

1. Makefile Modify and system call definitions

1. stay Makefile Add $U/_mmaptest
   
2. Add something about mmap and munmap Definition declaration of system call . Include kernel/syscall.h, kernel/syscall.c, user/usys.pl and user/user.h.
   
   
   
   
   

2. Definition vm_area Structure and its array

1. stay kernel/proc.h In the definition of struct vm_area Structure .
   vm_area namely Virtual Memory Area, VMA, Used here to indicate the use of mmap The location of the virtual memory area mapped by the system call file 、 size 、 Authority, etc ( In fact, Linux Will be used to represent the relevant information of the entire virtual memory area , Including heaps 、 Stack, etc. , In this part of the experiment, for simple consideration, it is only used to represent the memory of the file mapping part ).
   struct vm_area Memory information and mmap The parameters of the system call basically correspond to , Include the starting address of the mapping 、 Mapped memory length ( size )、 jurisdiction 、mmap Sign a 、 File offset and pointer to the file structure .

// Virtual Memory Area - lab10
struct vm_area {
    
    uint64 addr;    // mmap address
    int len;    // mmap memory length
    int prot;   // permission
    int flags;  // the mmap flags
    int offset; // the file offset
    struct file* f;     // pointer to the mapped file
};

2. stay struct proc Define relevant fields in the structure .
   In simple , According to the tips of the experimental guidance , Use one for each process VMA Array to record mapped memory ( Actually according to Linux Related implementation of , The effect of using linked list will be better ).
   Defined here NVMA Express VMA Size of array . And in struct proc The structure defines vma Array , And easy to know VMA Is the private field of the process , So for xv6 Process single user threaded system , visit VMA There is no need to lock .

#define NVMA 16 // the number of VMA in a process - lab10

// Per-process state
struct proc {
    
  // ...
  struct inode *cwd;           // Current directory
  char name[16];               // Process name (debugging)
  struct vm_area vma[NVMA];    // VMA array - lab10
};

3. To write mmap system call

stay kernel/sysfile.c Realize system call in sys_mmap().

1. The first is the extraction of parameters , here mmap The parameters of Linux The contents in the manual are basically the same , because xv6 There are only integers for the numeric parameters of the system call in int Type extraction , therefore len, offset Parameters are defined here as int type .
2. Next is a simple check of parameters . Because in the experiment, only mmap System call file mapping section , therefore prot and flags There are few parameters . flags Parameter must be MAP_SHARED and MAP_PRIVATE A choice . And for MAP_SHARED Because it will be written to the file , Therefore, if the mapped file is not writable and used PROT_WRITE If you write the mapping permission, an error will be reported , because You cannot write to a non writable file . At the end of the day len and offset The nonnegativity of , as well as requirement offset yes PGSISZE Integer multiple ( reference Linux Limitations in the manual , In this experiment offset In fact, it's all 0).
3. Then from the current process VMA Assign a VMA structure , The allocation rules are also relatively simple , According to VMA The address recorded in , if 0 It means that VMA It can be used for this mapping without being used .
4. Next is this mmap The parameters of are recorded to the assigned VMA in , The first thing to consider is the address used for mapping . According to the experimental guidance , It can be assumed addr The parameters are 0, That is, the kernel needs to choose the mapped address by itself .
   Here, , The author refers to Linux Memory layout , stay kernel/memlayout.h It defines MMAPMINADDR Macro definition , Used to represent mmap The lowest address that can be used for mapping . If this process has multiple file mappings , Therefore, when actually determining the mapped address , I'll go through it first VMA Array , Find the highest address of the mapped memory , Then take the address up and align the page , Then determine this mmap Mapping address of . Of course , If the mapped address space will cover TRAPFRAME May be an error . ( This is actually a relatively simple implementation , The problem that mapped memory may be released first from low addresses is not considered , But this implementation is more complex , It is necessary to calculate whether the unallocated space meets this allocation , Implement an algorithm similar to memory partitioning . In addition, there is no check that the heap space may cover the mapped memory , actually xv6 It may not cover the heap space TRAPFRAME Inspection , Maybe it's because we won't allocate so much memory , This may cause physical memory exhaustion .)
   According to the requirements of the experiment , mmap The mapping memory of is also Lazy allocation, So here you only need to VMA The address mapped in the record is the length , And the subsequent passage is in trap Chinese vs page fault Process the actual memory page allocation .

// the minimum address the mmap can ues - lab10
#define MMAPMINADDR (TRAPFRAME - 10 * PGSIZE)

5. Other parameters can be directly recorded in the assigned VMA In structure . For referenced file pointers , Need to use filedup() Increase the number of references , Avoid releasing its file structure .
6. Finally, return the assigned address . Any failure in the process returns 0xffffffffffffffff namely -1.

// lab10
uint64 sys_mmap(void) {
    
  uint64 addr;
  int len, prot, flags, offset;
  struct file *f;
  struct vm_area *vma = 0;
  struct proc *p = myproc();
  int i;

  if (argaddr(0, &addr) < 0 || argint(1, &len) < 0
      || argint(2, &prot) < 0 || argint(3, &flags) < 0
      || argfd(4, 0, &f) < 0 || argint(5, &offset) < 0) {
    
    return -1;
  }
  if (flags != MAP_SHARED && flags != MAP_PRIVATE) {
    
    return -1;
  }
  // the file must be written when flag is MAP_SHARED
  if (flags == MAP_SHARED && f->writable == 0 && (prot & PROT_WRITE)) {
    
    return -1;
  }
  // offset must be a multiple of the page size
  if (len < 0 || offset < 0 || offset % PGSIZE) {
    
    return -1;
  }

  // allocate a VMA for the mapped memory
  for (i = 0; i < NVMA; ++i) {
    
    if (!p->vma[i].addr) {
    
      vma = &p->vma[i];
      break;
    }
  }
  if (!vma) {
    
    return -1;
  }

  // assume that addr will always be 0, the kernel 
  //choose the page-aligned address at which to create
  //the mapping
  addr = MMAPMINADDR;
  for (i = 0; i < NVMA; ++i) {
    
    if (p->vma[i].addr) {
    
      // get the max address of the mapped memory 
      addr = max(addr, p->vma[i].addr + p->vma[i].len);
    }
  }
  addr = PGROUNDUP(addr);
  if (addr + len > TRAPFRAME) {
    
    return -1;
  }
  vma->addr = addr;   
  vma->len = len;
  vma->prot = prot;
  vma->flags = flags;
  vma->offset = offset;
  vma->f = f;
  filedup(f);     // increase the file's reference count

  return addr;
}

4. To write page fault Processing code

Because in sys_mmap() The memory for file mapping in is Lazy allocation, Therefore, it is necessary to map the memory generated by accessing the file page fault To deal with . And before Lazy allocation and COW The experiment is the same , I.e. modification kernel/trap.c in usertrap() Code for .

1. The first is to add pairs page fault Situational trap The inspection of , Because mapped memory is not allocated , And the memory read and write execution is possible , So all types page fault Can happen , therefore r_scause() The values of include 12, 13 and 15 Three situations .
2. Next is based on the occurrence page fault Address to the current process VMA Find the corresponding... In the array VMA Structure .
   What needs to be added here is , according to mmap Of Linux manual , File mapping parameters length It can actually exceed the file ( from offset rise ) Size , and File mapping is in pages Of , So the corresponding The part that exceeds the actual size of the file , The content will be 0, You can access and modify , But it will not be written back to the file in the end . But look here VMA The upper limit of memory is through va < p->vma[i].addr + p->vma[i].len To compare ( No increase PGROUNDUP() Because va In advance PGROUNDDOWN() Rounding down ).
   Find the corresponding VMA This time page fault It is caused by accessing the memory mapped by the file , And then continue the following work .
3. And then to Store Page fault Make a separate judgment , Skip here , This part is used for dirty page flag bit (PTE_D) Set up , In the subsequent unified elaboration .
4. And then there's going to be Lazy allocation, Use kalloc() First allocate a physical page , And use memset() To empty ( This step is necessary , kalloc() The allocated page is initially full 0x5 Dirty data ).
5. Then use readi() According to occurrence page fault The address of reads the contents from the corresponding part of the file to the allocated physical page . The size read here is PGSIZE, If the file size exceeds readi() The interior will be intercepted , Does not affect . Before and after this process, you need to check the file inode To lock .
6. After reading the file data , It is very important to set the access permission of this part , Access rights are based on VMA Recorded in the mmap Of prot Parameter to PTE Permission flag bit of . It is relatively simple for read and execute permissions , For write permission, only this time is Store Page fault Will be set when , For specific reasons, see the description of the flag bit of the subsequent dirty page .
7. Finally, you can use mappages() Map the physical page to the page value of the user process .

void
usertrap(void)
{
    
  // ...
  if(r_scause() == 8){
    
    // ...
  } else if (r_scause() == 12 || r_scause() == 13
             || r_scause() == 15) {
     // mmap page fault - lab10
    char *pa;
    uint64 va = PGROUNDDOWN(r_stval());
    struct vm_area *vma = 0;
    int flags = PTE_U;
    int i;
    // find the VMA
    for (i = 0; i < NVMA; ++i) {
    
      // like the Linux mmap, it can modify the remaining bytes in
      //the end of mapped page
      if (p->vma[i].addr && va >= p->vma[i].addr
          && va < p->vma[i].addr + p->vma[i].len) {
    
        vma = &p->vma[i];
        break;
      }
    }
    if (!vma) {
    
      goto err;
    }
    // set write flag and dirty flag to the mapped page's PTE
    if (r_scause() == 15 && (vma->prot & PROT_WRITE)
        && walkaddr(p->pagetable, va)) {
    
      if (uvmsetdirtywrite(p->pagetable, va)) {
    
        goto err;
      }
    } else {
    
      if ((pa = kalloc()) == 0) {
    
        goto err;
      }
      memset(pa, 0, PGSIZE);
      ilock(vma->f->ip);
      if (readi(vma->f->ip, 0, (uint64) pa, va - vma->addr + vma->offset, PGSIZE) < 0) {
    
        iunlock(vma->f->ip);
        goto err;
      }
      iunlock(vma->f->ip);
      if ((vma->prot & PROT_READ)) {
    
        flags |= PTE_R;
      }
      // only store page fault and the mapped page can be written
      //set the PTE write flag and dirty flag otherwise don't set
      //these two flag until next store page falut
      if (r_scause() == 15 && (vma->prot & PROT_WRITE)) {
    
        flags |= PTE_W | PTE_D;
      }
      if ((vma->prot & PROT_EXEC)) {
    
        flags |= PTE_X;
      }
      if (mappages(p->pagetable, va, PGSIZE, (uint64) pa, flags) != 0) {
    
        kfree(pa);
        goto err;
      }
    }
  }else if((which_dev = devintr()) != 0){
    
    // ok
  } else {
    
err:
    printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
    printf(" sepc=%p stval=%p\n", r_sepc(), r_stval());
    p->killed = 1;
  }
  // ...
}  

5. To write munmap system call

stay kernel/sysfile.c Realize system call in sys_munmap(). According to the requirements of the experiment , The system calls part of the memory to be mapped to unmap , At the same time, if MAP_SHARED You need to Changes to the file mapped memory will be written to the file ( stay Linux in , Being able to write documents is mmap autocomplete , Different from this experiment ).

1. The first is the extraction of parameters , munmap Only addr and length Two parameters .
2. Then simply check the parameters . len Non negative required ; Besides, according to Linux manual , addr Need to be PGSIZE Integer multiple .
3. Next, the same usertrap() It's similar to , according to addr and length Find for VMA Structure . If it is not found, it will return failure .
4. Then it is mainly to judge whether the current unmapped part has MAP_SHARED Sign a , If so, you need to write this part back to the file . Of course, before that, judge len Is it 0, If so, it will directly return to success , No follow-up work is required .
   This part is the most complex part of the system call , There are two things to consider : First, which pages need to be written , The other is the write size of each write back file . For the former , According to the experimental guidance , Choose to use the dirty page flag bit (PTE_D) For recording , Having this flag indicates that the modified part has been modified , You need to write the page back to the file , For the specific setting of dirty page flag bit, see the following . For the latter , Because the document will be written according to the dirty page , Therefore, it is conceivable that the write size is PGSIZE, But because of len Probably not. PGSIZE Integer multiple , Judgment is also needed here . Besides , According to the experimental guidance , Reference resources filewrite() function , The size of the file written at a time is also affected by the log block Influence , Therefore, the file may be written in batches ( actually PGSIZE Greater than maxsz, When the whole page needs to be written, it will be divided into two times ).
5. After writing the changes back to the file , You can use uvmunmap() Unmap some changed pages in the user page table .
   Here is the method of canceling page table mapping by rounding up the page , Actually, it feels a little unreasonable , Because some pages may not be unmapped , But considering that addr Need page alignment , Therefore, the file mapping will not be cancelled in the middle of the page , Otherwise, the latter half of the file cannot be unmapped .
   Besides , Modified here uvmunmap() Functional PTE_V Check part of flag bit , And before Lazy allocation The experiment is the same , Unmapped pages may not be actually allocated , Skip now .

void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
    
  // ...
  for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
    
    if((pte = walk(pagetable, a, 0)) == 0)
      panic("uvmunmap: walk");
    if((*pte & PTE_V) == 0) {
    
      continue;   // lab10
// panic("uvmunmap: not mapped"); // lab10
    }
    if(PTE_FLAGS(*pte) == PTE_V) {
    
      continue;   // lab10
// panic("uvmunmap: not a leaf");
    }
    // ...
  }
}

6. Finally, I need to update VMA Structure . Because the unmapped part of the file may just VMA Part of the file mapping memory in the structure , But according to the experimental guidance , The unmapped part will not be in the middle of the file mapping memory , That is, a new block of memory will not be generated due to the cancellation of file mapping , So just update the original VMA The relevant parameters of the structure can be . Throughout VMA When the memory recorded in the structure is unmapped , Then the VMA The structure is empty .

// lab10
uint64 sys_munmap(void) {
    
  uint64 addr, va;
  int len;
  struct proc *p = myproc();
  struct vm_area *vma = 0;
  uint maxsz, n, n1;
  int i;

  if (argaddr(0, &addr) < 0 || argint(1, &len) < 0) {
    
    return -1;
  }
  if (addr % PGSIZE || len < 0) {
    
    return -1;
  }

  // find the VMA
  for (i = 0; i < NVMA; ++i) {
    
    if (p->vma[i].addr && addr >= p->vma[i].addr
        && addr + len <= p->vma[i].addr + p->vma[i].len) {
    
      vma = &p->vma[i];
      break;
    }
  }
  if (!vma) {
    
    return -1;
  }

  if (len == 0) {
    
    return 0;
  }

  if ((vma->flags & MAP_SHARED)) {
    
    // the max size once can write to the disk
    maxsz = ((MAXOPBLOCKS - 1 - 1 - 2) / 2) * BSIZE;
    for (va = addr; va < addr + len; va += PGSIZE) {
    
      if (uvmgetdirty(p->pagetable, va) == 0) {
    
        continue;
      }
      // only write the dirty page back to the mapped file
      n = min(PGSIZE, addr + len - va);
      for (i = 0; i < n; i += n1) {
    
        n1 = min(maxsz, n - i);
        begin_op();
        ilock(vma->f->ip);
        if (writei(vma->f->ip, 1, va + i, va - vma->addr + vma->offset + i, n1) != n1) {
    
          iunlock(vma->f->ip);
          end_op();
          return -1;
        }
        iunlock(vma->f->ip);
        end_op();
      }
    }
  }
  uvmunmap(p->pagetable, addr, (len - 1) / PGSIZE + 1, 1);
  // update the vma
  if (addr == vma->addr && len == vma->len) {
    
    vma->addr = 0;
    vma->len = 0;
    vma->offset = 0;
    vma->flags = 0;
    vma->prot = 0;
    fileclose(vma->f);
    vma->f = 0;
  } else if (addr == vma->addr) {
    
    vma->addr += len;
    vma->offset += len;
    vma->len -= len;
  } else if (addr + len == vma->addr + vma->len) {
    
    vma->len -= len;
  } else {
    
    panic("unexpected munmap");
  }
  return 0;
}

6. Dirty page flag bit setting

As mentioned earlier , stay munmap When the system call writes the modified contents in the mapped memory back to the file , Only consider the parts that have been modified , That is, dirty pages are written back to files . This implementation has two benefits , On the one hand, it can reduce the data written back , about MAP_SHARED And writable files , Not all content is written back , Instead, write back only the modified part ; On the other hand , Because the file mapped memory is Lazy allocation, Dirty pages must have allocated memory because they have been modified , Therefore, it is unnecessary to consider whether the current page is actually allocated when unmapping .
stay xv6 in , Dirty pages can be accessed through PTE Dirty page flag bit PTE_D Are identified , however xv6 This part is not implemented by itself . Therefore, the author has simply implemented this part , Only the dirty page flag bit setting of file mapped memory pages is considered .

1. The first is kernel/riscv.h The dirty page flag bit is defined in PTE_D

#define PTE_D (1L << 7) // dirty flag - lab10

2. And then kernel/vm.c It defines uvmgetdirty() as well as uvmsetdirtywrite() Two functions . The former is used to read the dirty page flag bit , The latter is used to write dirty page flag bit and write flag bit ( Because the two flag bits are updated at the same time ). Because back PTE Of walk() Is an internal function , All the functions defined here are specially used for reading and writing dirty page flag bits .

// get the dirty flag of the va's PTE - lab10
int uvmgetdirty(pagetable_t pagetable, uint64 va) {
    
  pte_t *pte = walk(pagetable, va, 0);
  if(pte == 0) {
    
    return 0;
  }
  return (*pte & PTE_D);
}

// set the dirty flag and write flag of the va's PTE - lab10
int uvmsetdirtywrite(pagetable_t pagetable, uint64 va) {
    
  pte_t *pte = walk(pagetable, va, 0);
  if(pte == 0) {
    
    return -1;
  }
  *pte |= PTE_D | PTE_W;
  return 0;
}

3. Next is about how to set the dirty page flag bit . The idea is also simple , and COW The mechanism is somewhat similar , It is using page fault Set the dirty page flag bit . For dirty pages , That is, there are modified pages , Its page permissions must be writable , So consider writing a page for the first time by trap Handle the PTE Add the dirty page flag bit . There are two main scenarios :
   One is Write to unmapped writable pages , According to the foregoing , At this point will pass trap Allocate physical pages , namely Lazy allocation. Due to triggering this page fault It's a write operation , Therefore, subsequent instructions will certainly modify the content of this page , So add to PTE_D Dirty page flag bit .
   The other is Read or perform operations on unmapped writable pages , At this time, physical pages will also be allocated , But although the page can be written , But this is a read operation , The content of the page has not been modified , Therefore, you cannot add PTE_D Sign a , Add when you need to continue writing . So at this time , and Not set up PTE Write flag bit PTE_W, So the page is currently not writable , If you write to the page later, it will trigger again page fault, At this time, add the write flag bit and dirty page flag bit .
   The specific code is in the above steps #4 Of kernel/trap.c Of usertrap() in . Read / write operations mentioned above , Can pass r_scause() The return value of ; And steps #4 Find the corresponding VMA The code behind the structure if (r_scause() == 15 && (vma->prot & PROT_WRITE) && walkaddr(p->pagetable, va)) It is used to distinguish the above two situations , r_scause() by 15 namely Store Page fault, Write operations , here VMA The mapped memory recorded in needs to be equally writable , And walkaddr() Return non 0 Value indicates that memory has been allocated to the page . This is the second case used to trigger again page fault Judge when . else Clause is the step #4 Describe the page allocation process , And through code if (r_scause() == 15 && (vma->prot & PROT_WRITE)) Set the dirty page flag bit and write flag bit , Corresponding to the first case above .
4. stay usertrap() The dirty page flag bit is set in , Follow up munmap() You can call uvmgetdirty() To determine whether the page has been modified .

7. modify exit and fork system call

The above content completes the basic mmap and munmap Part of system call . Finally, we need to exit and fork Two system calls to modify , Add memory mapping to process files and VMA Array processing .

1. modify kernel/proc.c Medium exit() function .
   When the process exits , Need to look like munmap() Unmap the memory of the file mapping part . So the added code is similar to munmap() Part of the basic system , The difference is that you need to traverse VMA Array unmaps all file mapped memory , And the whole part is cancelled .

void
exit(int status)
{
    
  // ...
  if(p == initproc)
    panic("init exiting");

  // unmap the mapped memory - lab10
  for (i = 0; i < NVMA; ++i) {
    
    if (p->vma[i].addr == 0) {
    
      continue;
    }
    vma = &p->vma[i];
    if ((vma->flags & MAP_SHARED)) {
    
      for (va = vma->addr; va < vma->addr + vma->len; va += PGSIZE) {
    
        if (uvmgetdirty(p->pagetable, va) == 0) {
    
          continue;
        }
        n = min(PGSIZE, vma->addr + vma->len - va);
        for (r = 0; r < n; r += n1) {
    
          n1 = min(maxsz, n - i);
          begin_op();
          ilock(vma->f->ip);
          if (writei(vma->f->ip, 1, va + i, va - vma->addr + vma->offset + i, n1) != n1) {
    
            iunlock(vma->f->ip);
            end_op();
            panic("exit: writei failed");
          }
          iunlock(vma->f->ip);
          end_op();
        }
      }
    }
    uvmunmap(p->pagetable, vma->addr, (vma->len - 1) / PGSIZE + 1, 1);
    vma->addr = 0;
    vma->len = 0;
    vma->offset = 0;
    vma->flags = 0;
    vma->offset = 0;
    fileclose(vma->f);
    vma->f = 0;
  }

  // Close all open files.
  for(int fd = 0; fd < NOFILE; fd++){
    
    if(p->ofile[fd]){
    
      struct file *f = p->ofile[fd];
      fileclose(f);
      p->ofile[fd] = 0;
    }
  }
  // ...
}

2. modify kernel/proc.c Medium fork() function .
   In the use of fork() When creating a subprocess , The parent process's VMA Copy the structure , To get the same file mapped memory . Because the file mapping memory is used Lazy allocation, So the processing at this time can be relatively simple , Directly to the parent process VMA Just copy the array , When a child process uses a file to map memory, it will pass page fault Allocate pages .
   Of course , Here you can optimize , use COW The mechanism allows parent-child processes to point to the same file to map physical pages , It is very convenient to map memory for non writable files , And the writable memory is through COW The mechanism is updated again . Here the author did not optimize .

int
fork(void)
{
    
  // ...
  // increment reference counts on open file descriptors.
  for(i = 0; i < NOFILE; i++)
    if(p->ofile[i])
      np->ofile[i] = filedup(p->ofile[i]);
  np->cwd = idup(p->cwd);

  // copy all of VMA - lab10
  for (i = 0; i < NVMA; ++i) {
    
    if (p->vma[i].addr) {
    
      np->vma[i] = p->vma[i];
      filedup(np->vma[i].f);
    }
  }

  safestrcpy(np->name, p->name, sizeof(p->name));
  // ...
}

Have a problem

• stay xv6 In the implementation of mmaptest, among fork_test The following error appears :
  
  solve : according to mmap(4) You can go to user/mmaptest.c Where the error occurred in , as a result of mmap() Return failed . Through analysis, it is found that this is a read-only file MAP_SHARED Form mapping . At first, the author only judged MAP_SHARED Flag bit and file reading and writing mmap Can we continue , But for no PROT_WRITE File mapping of permissions , Although there are MAP_SHARED Sign a , But it will not be written to the file , Therefore, it should also be possible to continue , Therefore, the correct approach should be to add permissions to the mapping prot & PROT_WRITE The inspection of , See the above for the specific code sys_mmap() Realization .
  
  

test

• stay xv6 In the implementation of mmaptest test :
  
• stay xv6 In the implementation of usertests test :
  
• perform make grade test :