utilities

用时 5h 左右.

Boot xv6

配环境配了半个多小时。官网的引导还是非常清晰的。

sleep

xv6 系统 exec指令时，创建一个子进程执行该用户指令，用户函数中可能会有系统调用。这时会陷入内核态并进行操作，再返回。全部执行完后要 exit 来让进程退出。

调用系统调用 sleep.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include "kernel/types.h"
#include "user/user.h"

int main(int argc, char* argv[])
{
    if (argc < 2) {
        char* str;
        str = "Usage: sleep sleeptime..\n";
        write(1, str, strlen(str));
        exit(0);
    }
    int time = atoi(argv[1]);
    sleep(time);
    exit(0);
}

注意标准输入的 fd 号是 0，标准输出是 1，错误输出（stderr）是 2.

其中，系统调用 sleep(time) 将当前进程挂起 (time) 个 tick. 如果 sleep 过程中发生信号中断，会返回剩余没睡完的时间。

可能看书不仔细，没有找到 qemu 模拟的一个 tick 是多久。Linux 下的 sleep() 不是按 tick 睡而是按秒睡。

pingpong

该任务要求用 pipe 实现父进程和子进程的通信，子进程写一个 byte 发送给父进程。

pipe() 会创建一个管道，占用两个文件描述符 fd[2]，fd[0] 用于读，fd[1] 用于写。fork() 之后父进程 wait() 一下，等子进程做完它的事再去管道读。

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
#include "kernel/types.h"
#include "user/user.h"

int main(int argc, int *argv[]) {
    int fd[2];
    if (pipe(fd) < 0) {
        fprintf(2, "Pipe creation failed\n");
        exit(1);
    }
    int pid;
    if (!(pid = fork())) {
        fprintf(1, "%d: received ping\n", getpid());
        write(fd[1], "x", 1);
    }
    else {
        wait(0);
        fprintf(1, "%d: received pong\n", getpid());
        char *buf = malloc(sizeof(char));
        read(fd[0], buf, 1);
        fprintf(1, "message %s received\n", buf);
        free(buf);
    }
    close(fd[0]);
    close(fd[1]);
    exit(0);
}

primes

用 pipeline 求素数。题目说求 35 以内的就可以，但是测的时候求 100 多也没问题。做法是在每次递归时，将待筛选的数输入 pipe 内，让下一层递归读取并筛去，筛完的数再递归到下一层。

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
#include "kernel/types.h"
#include "user/user.h"

void test_prime(int fd) {
    int num, p;
    int rd;
    if ((rd = read(fd, &num, 4)) && rd != 4) {
        // end of recursion
        fprintf(2, "pipe read is not in int type\n");
        exit(0);
    }
    else if (!rd) exit(0);

    fprintf(1, "prime %d\n", num);
    int son_fd[2];

    pipe(son_fd);
    if (!fork()) { // child
        close(fd);
        close(son_fd[1]);
        test_prime(son_fd[0]);
    }
    else {
        close(son_fd[0]);
        while ((rd = read(fd, &p, 4))) {
            if (rd != 4) {
                fprintf(2, "pipe read is not in int type\n");
                exit(1);
            }
            if (p % num) {
                write(son_fd[1], &p, 4);
            }
        }
        close(son_fd[1]);
        close(fd);
        wait(0);
        exit(0);
    }
}

int main(int argc, char *argv[]) {
    int fd[2];
    pipe(fd);
    int i, n = 35;
    for (i = 2; i <= n; ++i) { // initialize
        write(fd[1], &i, 4);
    }
    close(fd[1]);
    test_prime(fd[0]);
    exit(0);
}

find

照着 ls 写递归版本就行。要先熟悉 stat、dirent 等描述结构体。stat详细可以看 stat.h。dirent 描述的是当前被读取的目录信息，其中包括索引节点号 inum 和目录名 name.

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
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"

char*
fmtname(char *path)
{
  static char buf[DIRSIZ+1];
  char *p;

  // Find first character after last slash.
  for(p=path+strlen(path); p >= path && *p != '/'; p--)
    ;
  p++;

  // Return name.
  if(strlen(p) >= DIRSIZ)
    return p;
  memmove(buf, p, strlen(p));
  *(buf + strlen(p)) = 0;
  return buf;
}

void find(char* path, char* target) {
    char buf[512];
    char* p;
    int fd;
    struct dirent de;
    struct stat st;
    if ((fd = open(path, 0)) < 0) {
        fprintf(2, "find: cannot open %s\n", path);
        return;
    }
    if (fstat(fd, &st) < 0) {
        fprintf(2, "find: cannot stat %s\n", path);
        close(fd);
        return;
    }
    switch(st.type) {
        case T_FILE:
            // printf("%s is a file, fmtname: %s, target: %s\n", path, fmtname(path), target);
            if (!strcmp(target, fmtname(path))) {
                printf("%s\n", path);
            }
            break;
        case T_DIR:
        // printf("%s is a directory\n", path);
            if (strlen(path) + DIRSIZ + 1 + 1 > sizeof(buf)) {
                printf("find: path too long\n");
                break;
            }
            strcpy(buf, path);
            p = buf + strlen(buf);
            *p++ = '/';
            while (read(fd, &de, sizeof(de)) == sizeof(de)) {
                if (de.inum == 0) continue;
                memmove(p, de.name, DIRSIZ);
                p[DIRSIZ] = 0;
                if (!strcmp(de.name, ".") || !strcmp(de.name, ".."))
                    continue;
                find(buf, target);
            }
            break;
        default:
            break;
    }
    close(fd);
}

int main(int argc, char* argv[]) {
    if (argc != 3) {
        printf("Usage: find directory filename..\n");
        exit(0);
    }
    find(argv[1], argv[2]);
    exit(0);
}

xargs

模拟题。把当前标准输入中的内容存下来，接到 argv 后面，再在子进程中 exec 就可以了。

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
#include "kernel/types.h"
#include "kernel/param.h"
#include "user/user.h"

int main(int argc, char *argv[]) {
    char buf[512];

    // copy args to command ptr
    char *command[MAXARG];
    argc--;
    for (int i = 0; i < argc; ++i) {
        command[i] = argv[i + 1];
    }

    // read std input to buf, and append buf
    int input_size, argptr;
    while ((input_size = read(0, buf, sizeof(buf))) > 0) {
        argc++, argptr = 0;
        command[argc - 1] = malloc(64 * sizeof(char));
        for (int i = 0; i < input_size; ++i) {
            char ch = buf[i];
            if (ch == ' ') {
                argc++, argptr = 0;
                command[argc - 1] = malloc(64 * sizeof(char));
                if (argc > MAXARG) {
                    fprintf(2, "xargs: too many args!\n");
                    exit(1);
                }
            }
            else if (ch == '\n') {
                break;
            }
            else {
                command[argc - 1][argptr++] = ch;
            }
        }
    }

    // use childproc to execute the command follows xargs
    if (!fork()) {
        exec(argv[1], command);
    }
    else {
        wait(0);
    }
    exit(0);
}

最后 make grade 99 分，原来还需要上传一个完成时间。

echo 5 > time.txt && make grade

make grade，100/100

syscall

用时 4h 左右。

首先是 riscv64 gdb 的安装。直接 riscv64-unknown-elf-gdb 之后是这样：

1
riscv64-unknown-elf-gdb: command not found

先拷贝一份 gdb 源码到本地，再 mkdir build && cd build.

执行：

1
2
3
4
sudo apt install libgmp-dev
../configure --prefix=/usr/local --with-python=/usr/bin/python --target=riscv64-unknown-elf --enable-tui=yes
make -j$(nproc)
sudo make install

完成 riscv 版本 gdb 的安装。

再执行 riscv64-unknown-elf-gdb，就能启动 gdb 了。

（P.S. 做完 util 之后觉得 wsl2 太慢太卡了，还是要上 Ubuntu. 但是太久没用 Ubuntu, 到这一步花了我好几个小时 orz）

折腾完环境终于能进入正题了

Using gdb

在一个终端启动 make qemu-gdb，记录 tcp::26000

在另一个终端打开 gdb（riscv版或者 gdb-multiarch ）, 并输入

1
target remote localhost:26000

完成连接。进入 kernel

1
file kernel/kernel

然后按说明调试.

或者直接 gdb-multiarch -x .gdbinit

建议先阅读 xv6 books 的第四节。

问题答案：

Looking at the backtrace output, which function called syscall?

usertrap() in kernel/trap.c

What is the value of p->trapframe->a7 and what does that value represent? (Hint: look user/initcode.S, the first user program xv6 starts.)

  1. sys status. EXEC or EXIT. in start at user/initcode.S, a7 is assigned with SYS_EXEC.

What was the previous mode that the CPU was in?

usermode. check sstatus:

1
2
p/t $sstatus
$5 = 100010

(Here we do as instruction, and if we check ‘p’ we’ll get ‘value has been optimized out’. It’s because creation of *p is after our breakpoint! what a fool is me.)

Write down the assembly instruction the kernel is panicing at. Which register corresponds to the varialable num?

80002078: 00002903 lw s2,0(zero) # 0 <_entry-0x80000000>

s2.

Why does the kernel crash? Hint: look at figure 3-3 in the text; is address 0 mapped in the kernel address space? Is that confirmed by the value in scause above? (See description of scause in RISC-V privileged instructions)

check scause, $1 = 13.

13 represents a load page fault. That’s because we load data from addr 0. 0 is not avaliable. Kernel space begins at 0x80000000.

What is the name of the binary that was running when the kernel paniced? What is its process id (pid)?

initcode.

pid is 1.

use p/x *p.

System call tracing

看不太懂。。这是要干啥。跟着 hint，找到 syscall.c 下的

1
2
3
4
5
6
// Fetch the nth 32-bit system call argument.
void
argint(int n, int *ip)
{
  *ip = argraw(n);
}

获取系统调用的第 n 个参数。

然后还找到有个函数 myproc() 返回当前正在运行的进程的 proc 结构体。

在 proc 中新建一个掩码变量，获取进行的系统调用号后用掩码与一下就知道现在调用什么了。根据 hint，还要注意 fork 时为子进程也 copy 一下掩码这个变量。

另外怎么没有地方提起返回值的问题。这里测试程序其实是规定了 trace 返回 0 的。

commit](https://github.com/Eykenis/xv6-labs-2022/commit/68a932a62dd3d357da8e84c9a77d3046da12443f))

Sysinfo

该系统调用输出一个 sysinfo 结构体。其中包括空闲内存大小和使用中的进程数量两个信息。

先将 sysinfotest 加入，会编译失败。去 user.h 声明一下 sysinfo 的结构体和函数。

xv6 的内存管理

xv6 将内存以链表的形式将空闲空间组织起来。见 kalloc.c 中对 run 和 kmem 的定义。run 就是一个单链表的定义。

kmem 的三个参数中，freelist 为空闲页链表。我们可以在 kalloc 函数中窥见 kmem 的运作方式。注意到每次 kalloc 都必须加锁。因为页表相关属于临界操作。

我们可以照着写 freememcount 函数用于计算页表空闲大小。虽然这里我们不修改临界资源，但为了避免结果不一致，还是加锁为好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int
freememcount(void)
{
  uint64 freepg_cnt = 0;
  
  struct run* r;
  
  acquire(&kmem.lock);
  r = kmem.freelist;
  while (r) {
    r = r->next;
    freepg_cnt++;
  }
  release(&kmem.lock);

  return freepg_cnt * PGSIZE;
}

然后再来看proc.c. 所有的进程都在 struct proc proc[NPROC] 这个全局变量中，我们只需要遍历这个 proc 数组，然后看看状态不为 UNUSED 的有多少个就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
int
procnum(void)
{
  struct proc* p;
  int proc_count = 0;

  for (p = proc; p != &proc[NPROC]; p++) {
    if (p->state != UNUSED) {
      proc_count++;
    }
  }
  return proc_count;
}

现在还有一个问题，我们这些操作都是在内核空间做的，我们需要将信息拷贝至用户空间。参考 copyout 函数的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
uint64
sys_sysinfo(void)
{
  uint64 st;
  struct sysinfo info;
  struct proc *p = myproc();

  argaddr(0, &st); // first arg in sysinfo() (userspace)

  info.freemem = freememcount();
  info.nproc = procnum();

  if (copyout(p->pagetable, st, &info, sizeof(info)) < 0)
    return -1;
  return 0;
}

commit

Pgtbl

看了很久的 book

Speed up system calls

应该属于进程间共享内存方式的通信。要求在内核和用户程序之间创建一个只读页，然后将 struct syscall 存入只读页中 USYSCALL 映射的地址。

ugetpid() 实现：

1
2
3
4
5
ugetpid(void)
{
  struct usyscall *u = (struct usyscall *)USYSCALL;
  return u->pid;
}

也就是说我们要在进程创建时，将进程用户空间 USYSCALL 这个地址位置存入 usyscall 的内容。

观察 memlayout.h。

1
2
3
4
5
6
7
// riscv.h
#define PGSIZE 4096
#define MAXVA (1L << (9 + 9 + 9 + 12 - 1))
// memlayout.h
#define TRAMPOLINE (MAXVA - PGSIZE)
#define TRAPFRAME (TRAMPOLINE - PGSIZE)
#define USYSCALL (TRAPFRAME - PGSIZE)

xv6 使用 Sv39 RISC-V 架构，64 位虚拟地址只有低 39 位被使用。

在转换物理地址的过程中，虚拟地址高 27 位用于定位 PTE。PTE 将指向一个 44 位的带标记位的物理页号，然后虚拟地址的低 12 位为偏移。最后得到一个 56 位的物理地址。

所以，对于我们的进程，它拥有 2^39^ = 512G 空间，PGSIZE = 4M. 地址空间自顶向下分别为 trampoline(1 页)、trapframe(1 页)、heap, user stack 和 user text and data.

heap 是自顶向下增长的。所以，我们要将 usyscall 的内容存在堆底也就是进程虚拟地址的第三页。

hint 中的 mempages 即用于进行 proc 结构体中各个变量和地址空间的映射。

问题：写完之后 test，发生了 scause，signal=15，为 page fault. 访问页面出错了。

于是上 printf 调试大法。

最后发现子进程中 fork 会导致 ugetpid 运行缺页。

继续排查，发现是 allocproc 函数出了问题，应当在 proc_pagetable 之前就分配好 usyscall 的空间。因为proc_pagetable() 为进程各项分配页表映射。如果分配映射时 usyscall 还没被分配空间的话，肯定会导致 page fault.

又是一个不仔细导致的错误，有点低级。

再回顾整个 allocproc 过程：

  1. 薅一个空闲进程过来
  2. 为进程内指针分配物理空间（kalloc）
  3. 创建一个页表，进行页表映射，以此创建进程各个项的用户空间地址。
  4. 创建新的上下文。

问题：

Which other xv6 system call(s) could be made faster using this shared page? Explain how.

fork(). We add a pointer *proc in struct usyscall, then children could access there parent in USYSCALL page.

commit

Print a page table

主要参考 freewalk 函数。这个 freewalk 用于释放页表映射，过程中访问了各个页表。

看 freewalk 的时候注意了 freewalk 考虑了 riscv 的多级页表，会进行相应的递归调用。而且遇到 leaf 页表项会 panic. 这说明 freewalk 之前要先释放掉所有 leaf pagetable.

总之照着写就能写出来了。注意格式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void recur_vmprint(pagetable_t pagetable, int level){
  for (int i = 0; i < 512; ++i) {
    pte_t pte = pagetable[i];
    if ((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0) {
      uint64 child = PTE2PA(pte);
      for (int j = 0; j < level; ++j)
        printf(".. ");
      printf("..%d: pte %p pa %p\n", i, pte, child);
      recur_vmprint((pagetable_t)child, level + 1);
    }
    else if (pte & PTE_V){
      for (int j = 0; j < level; ++j)
        printf(".. ");
      printf("..%d: pte %p pa %p\n", i, pte, PTE2PA(pte));
    }
  }
}

void
vmprint(pagetable_t pagetable) {
  printf("page table %p\n", pagetable);
  recur_vmprint(pagetable, 0);
}

commit

问题：

Explain the output of vmprint in terms of Fig 3-4 from the text. What does page 0 contain? What is in page 2? When running in user mode, could the process read/write the memory mapped by page 1? What does the third to last page contain?

page 0 contains text and data seg.

page 2 contains stack. (page 1 as stack gurad)

SEE IN exec() IN exec.c

NO.

511 to 509: trampoline, trapframe, and usyscall.

so 509 contains the struct usyscall.

Detect which pages have been accessed

alloc: if so, PTE in TLB, PTE_V is true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
pte_t *
walk(pagetable_t pagetable, uint64 va, int alloc)
{
  if(va >= MAXVA)
    panic("walk");

  for(int level = 2; level > 0; level--) {
    pte_t *pte = &pagetable[PX(level, va)];
    if(*pte & PTE_V) {
      pagetable = (pagetable_t)PTE2PA(*pte);
    } else {
      if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
        return 0;
      memset(pagetable, 0, PGSIZE);
      *pte = PA2PTE(pagetable) | PTE_V;
    }
  }
  return &pagetable[PX(0, va)];
}

PTE_A: RISC-V privileged architecture manual Figure 4.15

image-20230525144139109

Be sure to clear PTE_A after checking if it is set. Otherwise, it won’t be possible to determine if the page was accessed since the last time pgaccess() was called (i.e., the bit will be set forever).

不是很理解这句？

或许是因为 pgaccess 本身也会为 PTE_A 置 1，需要清除？

Traps

RISC-V assemply

全是问题。了解 RISCV 汇编。

Which registers contain arguments to functions? For example, which register holds 13 in main’s call to printf?

a0, a1, a2, …

a2 holds printf.

Where is the call to function f in the assembly code for main? Where is the call to g? (Hint: the compiler may inline functions.)

call no f or g. JUST calculated the result as 12.

At what address is the function printf located?

0x642

What value is in the register ra just after the jalr to printf in main?

0x38 the return address.

Run the following code.

1
2
3
unsigned int i = 0x00646c72;
printf("H%x Wo%s", 57616, &i);

What is the output? Here’s an ASCII table that maps bytes to characters.

The output depends on that fact that the RISC-V is little-endian. If the RISC-V were instead big-endian what would you set i to in order to yield the same output? Would you need to change 57616 to a different value?

Here’s a description of little- and big-endian and a more whimsical description.

In the following code, what is going to be printed after 'y='? (note: the answer is not a specific value.) Why does this happen?

1
printf("x=%d y=%d", 3);

>

Backtrace

了解程序栈的构造就很好写了。

主要还是读 xv6 book.

按照 hint 写 r_fp() 函数获取当前函数栈帧。

获取栈帧后，PGROUNDUP 一下获取栈底（xv6 的栈结构为向下增长）。当前栈帧 -8 所指向的位置是当前函数的返回地址，而指向的上一个地址是前一个被调用函数的帧地址。于是 fp-8 就可以获得当前函数返回地址，而 fp-16 就可以返回前一个函数帧。

1
2
3
4
5
6
7
8
9
10
11
12
void backtrace(void)
{
  uint64 fp, top;
  fp = r_fp();
  top = PGROUNDUP(fp);
  printf("backtrace:\n");
  while (fp != top)
  {
    printf("%p\n", *(uint64*)(fp - 8));
    fp = *(uint64*)(fp - 16);
  }
}

Alarm

Copy-on-Write

这次实验就解决一个问题：

如何用写时复制技术实现 fork() 。

先看开头的 solution，它提到我们在这次实验中要做的：内存懒分配。只在内存真的被需要的时候才从子进程复制一份过来。

  1. fork() 为子进程创建一个页表，页表项从子进程的虚拟页指向父进程的物理页。
  2. 子进程和父进程的页表项都标记为 read-only
  3. 标记后，两个进程其中任一尝试写这些页表时，都会触发 page fault.
  4. page fault 被内核 handler 侦测后，为 faulting process 分配一个物理页，复制原页面内容到新页面，将 PTE 指向这个新页面，并将 PTE 设置为 writable.
  5. 还没完！还有一些 free 相关的问题要解决。当一块物理页被多个进程使用时，我们不能随便 free，只有在最后一个使用这个页面的进程也不再使用时，我们才能 free. 解决办法是计数，类似 C++ 的智能指针。

子进程内存页不真的分配，只创建一组映射。同时要记录好映射这组物理页的计数。修改 uvmcopy：

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
int
cow_uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;

  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");
    pa = PTE2PA(*pte);
    *pte = (*pte) & (~PTE_W); // mark as read-only
    *pte = (*pte) | PTE_RSWD; // low bit of RSW to represent COW
    flags = PTE_FLAGS(*pte);
    if(mappages(new, i, PGSIZE, (uint64)pa, flags) != 0){
      goto err;
    }
    add_ref(pa); // add ref count. MIND that it is a criticial operation, so use lock.
  }
  return 0;

 err:
  uvmunmap(new, 0, i / PGSIZE, 1);
  return -1;
}

添加一个结构体用于每个页面的引用计数。

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
struct refcounter {
  struct spinlock lock;
  int cnt;
}pageref[PHYSTOP / PGSIZE];

int add_ref(uint64 pa, int x){
  acquire(&(pageref[pa / PGSIZE].lock));
  pageref[pa / PGSIZE].cnt += x;
  relese(&(pageref[pa / PGSIZE].lock));
  return 1;
}

int get_ref(uint64 pa){
  int ret;
  acquire(&(pageref[pa / PGSIZE].lock));
  ret = pageref[pa / PGSIZE].cnt;
  relese(&(pageref[pa / PGSIZE].lock));
  return ret;
}
void lock_ref(uint64 pa) {
  acquire(&(pageref[pa / PGSIZE].lock));
}

void release_ref(uint64 pa) {
  release(&(pageref[pa / PGSIZE].lock));
}

修改 kfree 和 kalloc，与引用计数相关。只有 ref cnt = 1 才释放。

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
void
kfree(void *pa)
{
  if (get_ref((uint64)pa) > 1) {
    add_ref((uint64)pa, -1);
    return;
  }

  struct run *r;

  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");

  // Fill with junk to catch dangling refs.
  memset(pa, 1, PGSIZE);

  r = (struct run*)pa;

  acquire(&kmem.lock);
  r->next = kmem.freelist;
  kmem.freelist = r;
  release(&kmem.lock);
}

void *
kalloc(void)
{
  struct run *r;

  acquire(&kmem.lock);
  r = kmem.freelist;
  if(r)
    kmem.freelist = r->next;
  release(&kmem.lock);

  if(r){
    memset((char*)r, 5, PGSIZE); // fill with junk
    add_ref((uint64)r, 1);
  }
  return (void*)r;
}