Xv6 Lab lazy page allocation

发表于

「这是我参与11月更文挑战的第25天，活动详情查看：2021最后一次更文挑战」

Meaning Unknown's Head Image

Lab: xv6 lazy page allocation

pdos.csail.mit.edu/6.S081/2020…

新的 2020 版哦。

1
2
3
sh复制代码$ git fetch
$ git checkout lazy
$ make clean

Eliminate allocation from sbrk()

这道题就是把 sys_sbrk 里的 growproc 调用删了，等用到的时候再去分配内存。如果是空间减小，要取消分配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
c复制代码uint64
sys_sbrk(void)
{
  int addr;
  int n;
  struct proc *p = myproc();  //(+)

  if(argint(0, &n) < 0)
    return -1;
  addr = p->sz;  // old sz
  p->sz += n;
  if (n < 0) {  // 空间减小: 取消分配
    uvmdealloc(p->pagetable, addr, p->sz);
  }
  return addr;
}

Lazy allocation

在 vm.c 里面实现惰性分配（莫忘在 defs.h 中声明函数）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
c复制代码#include "spinlock.h" //(+)
#include "proc.h"     //(+)

// lazy allocation memory va for proc p: handle page-fault.
// return allocated memory (pa), 0 for failed 
uint64 lazyalloc(struct proc * p, uint64 va){
  if(va >= p->sz || va < PGROUNDUP(p->trapframe->sp)){
    return 0;
  }
  char * mem;
  uint64 a = PGROUNDDOWN(va);
  mem = kalloc();
  if(mem == 0){
    return 0;
  }
  memset(mem, 0, PGSIZE);  
    if(mappages(p->pagetable, a, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
      kfree(mem);
      return 0;
    }

  return (uint64)mem;
}

在 usertrap (trap.c) 里处理缺页错误，尝试惰性分配（掉上面写的那个函数，失败就杀掉进程）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
c复制代码void
usertrap(void)
{
  ...
  if(r_scause() == 8){
    // system call
    ...
  } else if((which_dev = devintr()) != 0){
    // ok
  } else if((r_scause() == 13) || (r_scause() == 15)){  // page fault: (+)
  if (lazyalloc(myproc(), r_stval()) <= 0) {
    p->killed = 1;
  }
  } else {
    ...
  }
  ...
}

最后改一点点细节，把各种缺页会爆出的 panic 干掉（vm.c里）。以前这些情况正常是不会发生的，但现在惰性分配会带来缺页，所以要告诉操作系统遇到这些事情时 don’t panic，继续往下跑就行了：

（这里的代码我懒得改结构就上goto了，但你应该去改if结构，而不是goto）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
c复制代码// vm.c
...

//(+)
uint64
walkaddr(pagetable_t pagetable, uint64 va)
{
  ...

  if(pte == 0)
    goto lzac;
  if((*pte & PTE_V) == 0)
    goto lzac;
  if((*pte & PTE_U) == 0)
    goto lzac;
  pa = PTE2PA(*pte);
 
  if (0) {
lzac:
    if ((pa = lazyalloc(myproc(), va)) <= 0)
      pa = 0;
  }
  
  return pa;
}

int
mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)
{
  ...
  for(;;){
    ...
    if(*pte & PTE_V)
      // panic("remap");
      ;
    ...
}

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");
      continue;
    }
    if((*pte & PTE_V) == 0) {
      // panic("uvmunmap: not mapped");
      continue;
    }
    ...
  }
}
    
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  ...
  for(i = 0; i < sz; i += PGSIZE){
    if((pte = walk(old, i, 0)) == 0){
      // panic("uvmcopy: pte should exist");
      continue;
    }
    if((*pte & PTE_V) == 0){
      // panic("uvmcopy: page not present");
      continue;
    }
    ...
  }
  ...
}

测试

写的时候可以按题目跑这些测试：

1
2
3
4
sh复制代码xv6-labs-2020 $ make qemu
$ echo hi
$ lazytests
$ usertests

diff

详细的 git diff (可以用来做 patch 喔):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
diff复制代码diff --git a/kernel/defs.h b/kernel/defs.h
index 4b9bbc0..7ff16c4 100644
--- a/kernel/defs.h
+++ b/kernel/defs.h
@@ -171,6 +171,7 @@ uint64          walkaddr(pagetable_t, uint64);
 int             copyout(pagetable_t, uint64, char *, uint64);
 int             copyin(pagetable_t, char *, uint64, uint64);
 int             copyinstr(pagetable_t, char *, uint64, uint64);
+uint64          lazyalloc(struct proc * p, uint64 va);
 
 // plic.c
 void            plicinit(void);
diff --git a/kernel/sysproc.c b/kernel/sysproc.c
index e8bcda9..b799722 100644
--- a/kernel/sysproc.c
+++ b/kernel/sysproc.c
@@ -43,12 +43,15 @@ sys_sbrk(void)
 {
   int addr;
   int n;
+  struct proc *p = myproc();
 
   if(argint(0, &n) < 0)
     return -1;
-  addr = myproc()->sz;
-  if(growproc(n) < 0)
-    return -1;
+  addr = p->sz;  // old sz
+  p->sz += n;
+  if (n < 0) {
+    uvmdealloc(p->pagetable, addr, p->sz);
+  }
   return addr;
 }
 
diff --git a/kernel/trap.c b/kernel/trap.c
index a63249e..fc08231 100644
--- a/kernel/trap.c
+++ b/kernel/trap.c
@@ -67,6 +67,11 @@ usertrap(void)
     syscall();
   } else if((which_dev = devintr()) != 0){
     // ok
+  } else if((r_scause() == 13) || (r_scause() == 15)){  // page fault
+	// lazy allocation
+	if (lazyalloc(myproc(), r_stval()) <= 0) {
+	  p->killed = 1;
+	}
   } else {
     printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
     printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
diff --git a/kernel/vm.c b/kernel/vm.c
index bccb405..f3235c3 100644
--- a/kernel/vm.c
+++ b/kernel/vm.c
@@ -5,6 +5,8 @@
 #include "riscv.h"
 #include "defs.h"
 #include "fs.h"
+#include "spinlock.h"
+#include "proc.h"
 
 /*
  * the kernel's page table.
@@ -102,12 +104,19 @@ walkaddr(pagetable_t pagetable, uint64 va)
 
   pte = walk(pagetable, va, 0);
   if(pte == 0)
-    return 0;
+	goto lzac;
   if((*pte & PTE_V) == 0)
-    return 0;
+    goto lzac;
   if((*pte & PTE_U) == 0)
-    return 0;
+    goto lzac;
   pa = PTE2PA(*pte);
+ 
+  if (0) {
+lzac:
+	  if ((pa = lazyalloc(myproc(), va)) <= 0)
+		pa = 0;
+  }
+  
   return pa;
 }
 
@@ -157,7 +166,8 @@ mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)
     if((pte = walk(pagetable, a, 1)) == 0)
       return -1;
     if(*pte & PTE_V)
-      panic("remap");
+      // panic("remap");
+	  ;
     *pte = PA2PTE(pa) | perm | PTE_V;
     if(a == last)
       break;
@@ -180,10 +190,14 @@ uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
     panic("uvmunmap: not aligned");
 
   for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
-    if((pte = walk(pagetable, a, 0)) == 0)
-      panic("uvmunmap: walk");
-    if((*pte & PTE_V) == 0)
-      panic("uvmunmap: not mapped");
+    if((pte = walk(pagetable, a, 0)) == 0) {
+      // panic("uvmunmap: walk");
+	  continue;
+	}
+    if((*pte & PTE_V) == 0) {
+      // panic("uvmunmap: not mapped");
+	  continue;
+	}
     if(PTE_FLAGS(*pte) == PTE_V)
       panic("uvmunmap: not a leaf");
     if(do_free){
@@ -314,10 +328,14 @@ uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
   char *mem;
 
   for(i = 0; i < sz; i += PGSIZE){
-    if((pte = walk(old, i, 0)) == 0)
-      panic("uvmcopy: pte should exist");
-    if((*pte & PTE_V) == 0)
-      panic("uvmcopy: page not present");
+    if((pte = walk(old, i, 0)) == 0){
+      // panic("uvmcopy: pte should exist");
+	  continue;
+	}
+    if((*pte & PTE_V) == 0){
+      // panic("uvmcopy: page not present");
+	  continue;
+	}
     pa = PTE2PA(*pte);
     flags = PTE_FLAGS(*pte);
     if((mem = kalloc()) == 0)
@@ -440,3 +458,40 @@ copyinstr(pagetable_t pagetable, char *dst, uint64 srcva, uint64 max)
     return -1;
   }
 }
+
+
+// lazy allocation memory va for proc p: handle page-fault.
+// return allocated memory (pa), 0 for failed 
+uint64 lazyalloc(struct proc * p, uint64 va){
+#define lazyalloc_debug 0
+#define lazyalloc_warn(info) { \
+	  printf("lazyalloc(): %s", info); \
+      printf("             scause %p pid=%d\n", r_scause(), p->pid); \
+      printf("             sepc=%p stval=%p\n", r_sepc(), r_stval()); \
+}
+	if(va >= p->sz || va < PGROUNDUP(p->trapframe->sp)){
+	  #if lazyalloc_debug
+	    lazyalloc_warn("vm addr higher then any allocated with sbrk\n");
+      #endif
+	  return 0;
+	}
+	char * mem;
+	uint64 a = PGROUNDDOWN(va);
+	mem = kalloc();
+	if(mem == 0){
+	  #if lazyalloc_debug
+	    lazyalloc_warn("kalloc() == 0\n");
+      #endif
+	  return 0;
+	}
+	memset(mem, 0, PGSIZE);  
+    if(mappages(p->pagetable, a, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
+	  #if lazyalloc_debug
+ 	    lazyalloc_warn("mappages() != 0\n");
+      #endif
+	  kfree(mem);
+	  return 0;
+    }
+
+	return (uint64)mem;
+}

结果

最后 make grade 看成绩了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
sh复制代码xv6-labs-2020 $ make grade
...
== Test running lazytests == 
$ make qemu-gdb
(7.7s) 
== Test   lazy: map == 
  lazy: map: OK 
== Test   lazy: unmap == 
  lazy: unmap: OK 
== Test usertests == 
$ make qemu-gdb
(145.8s) 
== Test   usertests: pgbug == 
  usertests: pgbug: OK 
== Test   usertests: sbrkbugs == 
  usertests: sbrkbugs: OK 
== Test   usertests: argptest == 
  usertests: argptest: OK 
== Test   usertests: sbrkmuch == 
... OK ...
== Test   usertests: dirfile == 
  usertests: dirfile: OK 
== Test   usertests: iref == 
  usertests: iref: OK 
== Test   usertests: forktest == 
  usertests: forktest: OK 
== Test time == 
time: OK 
Score: 119/119

CDFMLR

顶部图片来自于网络，系随机选取的图片，仅用于检测屏幕显示的机械、光电性能，与文章的任何内容及观点无关，也并不代表本人局部或全部同意、支持或者反对其中的任何内容及观点。如有侵权，联系删除。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%