MIT 6.S081 - Lab Lock - Memory allocator - test

博主： Shirou
发布时间：2022 年 10 月 25 日
355 次浏览
暂无评论
14869字数
分类： os

MIT 6.S081 - Lab Lock - Memory allocator - test

代码传送门：OS_Learn/kalloc_test.c at main · xuanhao44/OS_Learn (github.com)

【仅包含部分代码，不能运行请自行查看文章补充相关内容】

本篇是我的测试过程，建议写完第一个 part 再来看。

1 某个思路：随机

freelist 和 cpuid 一定要对应起来吗？

既不对应，也不能从一个固定的位置去拿，应该怎么办？只能是随机了。

同时猜想：是不是在 kalloc 和 kfree 的时候足够随机就能避免竞争？大家的行为都会很随机，那这样竞争的概率不会很小吗？那么即使有多个 kalloc 和 kfree 同时发生，但是由于他们访问的 freelist 不同，所以不会产生很多锁争用。

在这种情况下，可初步预测：

开始 init 时，内存页被较均匀的分到了所有 freelist 的中。
在进程需要 kalloc 时，kalloc.c 从随机的一个 freelist 中为他找到一个 free page。
在进程需要 kfree 时，kalloc.c 找到随机的一个 freelist 放入进程释放的 page。

2 初步考虑随机相关问题

2.1 产生随机数

线性同余发生器：给出了产生随机数的例子。发现于 user/grind.c。

int do_rand(uint64 *ctx)
{
    long x = (*ctx % 0x7ffffffe) + 1;
    long hi = x / 127773;
    long lo = x % 127773;
    x = 16807 * lo - 2836 * hi;
    if (x < 0)
        x += 0x7fffffff;
    x--;
    *ctx = x;
    return x;
}

uint64 rand_next = 1;

int randN(void)
{
    return do_rand(&rand_next);
}

2.2 模数取决于 freelist 数量

产生的随机数很大，不是拿来直接用的。一般的做法是对其取模。

那么选什么当模数？模数取决于 freelist 的数量。设置为多少比较好呢？

2.2.1 实际运行的 CPU 个数

尝试设置为实际运行的 CPU 个数。

想在 xv6 中获取实际运行的 CPU 个数是困难的，只能从宏导入：

在 makefile 中添加参数，在 main.c 设置 CPU_NUM 获取，在 kalloc.c 中用 extern 使用。

makefile 中加上：

CFLAGS += -DCPUS=${CPUS}

kernel/main.c 中：（截取部分）

volatile static int started = 0;

int CPU_NUM = 0;

// start() jumps here in supervisor mode on all CPUs.
void
main()
{
  if(cpuid() == 0){
    consoleinit();
#if defined(LAB_PGTBL) || defined(LAB_LOCK)
    statsinit();
#endif
    printfinit();
    printf("\n");
    printf("xv6 kernel is booting\n");
    #if defined(CPUS)
      CPU_NUM = CPUS;
      printf("CPU_NUM = %d\n", CPU_NUM);
    #endif
    printf("\n");

kernel/kalloc.c 中：

extern int CPU_NUM; // from main.c
                    // defined by makefile

2.2.2 设置为较大的数

为什么 freelist 的数量一定要和实际 CPU 数量挂钩呢？这不太合理。我们完全可以设置为一个较大的数。

在下面的实验中，我们将设置为 300。

#define KMEMS 300

struct kmem
{
  struct spinlock lock;
  struct run *freelist;
} kmems[KMEMS];

实际上设置多少挺玄学的，要考虑到很多问题。接下来会提到一部分，但也不完全。

经测试发现：

在 CPU 数为 8 的情况下，KMEMS 高于某个值后，在编译 xv6 时就会 panic，该值为 315；
成功编译的情况下，KMEMS 高于某个值后，测试程序 usertests sbrkmuch 也会 panic，该值为 310；
上限值 315 和 310 与 CPU 数无关；不保证该值是准确值，不保证一直有效，仅供参考。
kalloctest test1 如果输出太多会崩掉，故去掉大量输出，下面是原因和调整方法。

user/kalloctest.c 片段：

#define NCHILD 2
#define N 100000
#define SZ 4096

void test1(void);
void test2(void);
char buf[SZ];

int
main(int argc, char *argv[])
{
  test1();
  test2();
  exit(0);
}

int ntas(int print)
{
  int n;
  char *c;

  if (statistics(buf, SZ) <= 0) {
    fprintf(2, "ntas: no stats\n");
  }
  c = strchr(buf, '=');
  n = atoi(c+2);
  if(print)
    printf("%s", buf);
  return n;
}

注意到 SZ 只有 4096，输出多起来就会出错。

于是把 kernel/spinlock.c:statslock() 的一个循环里输出 kmem.lock 的部分注释掉。

for(int i = 0; i < NLOCK; i++) {
    if(locks[i] == 0)
      break;
    if(strncmp(locks[i]->name, "bcache", strlen("bcache")) == 0 ||
       strncmp(locks[i]->name, "kmem", strlen("kmem")) == 0) {
      tot += locks[i]->nts;
      // n += snprint_lock(buf +n, sz-n, locks[i]);
    }
  }

这样输出就少了很多，当然 tot 的统计还是正常的，所以不影响最后的判断。

3 从一个错误百出的程序开始

让我们以这个程序为基础，一步步开始 ”优化“ 吧。

// Physical memory allocator, for user processes,
// kernel stacks, page-table pages,
// and pipe buffers. Allocates whole 4096-byte pages.

#include "types.h"
#include "param.h"
#include "memlayout.h"
#include "spinlock.h"
#include "riscv.h"
#include "defs.h"

void freerange(void *pa_start, void *pa_end);

extern char end[]; // first address after kernel.
                   // defined by kernel.ld.

int do_rand(uint64 *ctx)
{
  long x = (*ctx % 0x7ffffffe) + 1;
  long hi = x / 127773;
  long lo = x % 127773;
  x = 16807 * lo - 2836 * hi;
  if (x < 0)
    x += 0x7fffffff;
  x--;
  *ctx = x;
  return x;
}

uint64 rand_next = 1;

int randN(void)
{
  return do_rand(&rand_next);
}

struct run
{
  struct run *next;
};

#define KMEMS 300

struct kmem
{
  struct spinlock lock;
  struct run *freelist;
} kmems[KMEMS];

void kinit()
{
  for (int i = 0; i < KMEMS; i++)
    initlock(&kmems[i].lock, "kmems");

  freerange(end, (void *)PHYSTOP);
}

void freerange(void *pa_start, void *pa_end)
{
  char *p;
  p = (char *)PGROUNDUP((uint64)pa_start);
  for (; p + PGSIZE <= (char *)pa_end; p += PGSIZE)
    kfree(p);
}

// Free the page of physical memory pointed at by v,
// which normally should have been returned by a
// call to kalloc().  (The exception is when
// initializing the allocator; see kinit above.)
void kfree(void *pa)
{
  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;

  int id = randN() % KMEMS;
  acquire(&kmems[id].lock);
  {
    r->next = kmems[id].freelist;
    kmems[id].freelist = r;
  }
  release(&kmems[id].lock);
}

// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
void *
kalloc(void)
{
  struct run *r;
  int id;
  do
  {
    id = randN() % KMEMS;
    acquire(&kmems[id].lock);
    {
      r = kmems[id].freelist;
      if (r)
        kmems[id].freelist = r->next;
    }
    release(&kmems[id].lock);
  } while (!r);

  if (r)
    memset((char *)r, 5, PGSIZE); // fill with junk

  return (void *)r;
}

测试结果：kalloctest test1 没过，test2 根本无法开始；usertests sbrkmuch、usertests 也都卡住了！

3.1 不可完全随机的 kalloc

错误也许是显然的。

struct run *r;
int id;
do
{
  id = randN() % KMEMS;
  acquire(&kmems[id].lock);
  {
    r = kmems[id].freelist;
    if (r)
      kmems[id].freelist = r->next;
  }
  release(&kmems[id].lock);
} while (!r);

假设一种情况：使用的内存过多，各个 freelist 都没有多少 free page 了。

对应到这段代码，我们只是随机的选取了一个 freelist，然后去取它的 free page，如果没有的话就再次随机的选取一个 freelist。

然而各个 freelist 都没有多少 free page 了，故而随机选取一次，能找到 free page 的概率是很低的。

从整体上说，随着分配回收 free page 的进行，如果进程申请的内存比释放的 free page 多，所有 freelist 的 free page 是在不断减少的，随机选取一次，能找到 free page 的概率会降低；如果有 N 个 freelist 没有 free page 了，那么随机选取一次，能找到 free page 的概率就是 $(1 - N/{KMEMS})$。

既然不能完全随机，那么我们改变策略：

先随机选取一次；如果没有得到 free page，就遍历所有 freelist 去寻找 free page。

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

  int id = randN()  % KMEMS;
  acquire(&kmems[id].lock);
  {
    r = kmems[id].freelist;
    if (r)
      kmems[id].freelist = r->next;
  }
  release(&kmems[id].lock);

  // r = null, then steal from all freelist
  for (int i = 0; (!r) && (i < KMEMS); i++)
  {
    if (i == id)
      continue;

    acquire(&kmems[i].lock);
    {
      r = kmems[i].freelist;
      if (r)
        kmems[i].freelist = r->next;
    }
    release(&kmems[i].lock);
  }

  if (r)
    memset((char *)r, 5, PGSIZE); // fill with junk

  return (void *)r;
}

测试结果：修改得到的程序虽然不能过 test1，但是 test2、usertests sbrkmuch、usertests 可以通过。

3.2 随机是否起效

实际上，上面程序生成随机数 randN() % KMEMS 并没有起到应有的效果。进程共享着 uint64 rand_next，也就是说在多数时候，同时运行的 CPU 使用着相同的 rand_next，那么对于线性同余发生器来说得到的值就是相同的——这完全不是我们想要的。我们希望同时运行的 CPU 通过随机达成减少竞争，而这个想法根本没有被实现。

改进的方法是：为每一个 CPU 设置 rand_next，每一个 CPU 在获取随机数时需要使用自己的 rand_next。

uint64 rand_next[NCPU] = {1};

int randN(void)
{
  return do_rand(&rand_next[cpuid()]);
}

考虑一下为什么没有像平常那样关闭和打开中断：使用 cpuid 时，我们不在意 CPU 是否切换——这对随机数的生成并没有实质的影响。

测试结果：修改得到的程序不能过 test1，test2、usertests sbrkmuch、usertests 可以通过。但是 test1 的 tot 值明显的变小了很多。就是从上万到了两位数，这是个很大的进步！

tot 的值表现的很随机，在两位数到五位数之间波动。但是能到两位数了。

3.3 考虑锁：double check

一个可能出现的情况是所有 freelist 中剩余的 free page 不多。在这种情况下，很多加锁的步骤都是无效的，开销很大，且增加了很多锁争用。

采用 “不安全 check + 加锁 double check” 的处理模式：利用某些可以允许的不安全来换取缩小的锁范围，然后再使用额外的手段保证正确性。

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

  int id = randN() % KMEMS;
  // unsafe check
  if (kmems[id].freelist)
  {
    // acquire lock
    acquire(&kmems[id].lock);
    // double check
    if (kmems[id].freelist)
    {
      r = kmems[id].freelist;
      kmems[id].freelist = r->next;
    }
    release(&kmems[id].lock);
  }

  // r = null, then steal from all freelist
  for (int i = 0; (!r) && (i < KMEMS); i++)
  {
    if (i == id)
      continue;

    if (kmems[i].freelist)
    {
      // acquire lock
      acquire(&kmems[i].lock);
      // double check
      if (kmems[i].freelist)
      {
        r = kmems[i].freelist;
        kmems[i].freelist = r->next;
      }
      release(&kmems[i].lock);
    }
  }

  if (r)
    memset((char *)r, 5, PGSIZE); // fill with junk

  return (void *)r;
}

测试结果：修改得到的程序不能过 test1，test2、usertests sbrkmuch、usertests 可以通过。进一步优化的效果并不是很明显，tot 的值表现的很随机，在两位数到五位数之间波动。

3.4 考虑更随机的遍历

每次都从 0 开始不够随机，我们可以从 id + 1 开始遍历，充分利用了上面的随机数。

int j;
for (int i = 0; (!r) && (i < KMEMS); i++)
{
  j = (id + 1 + i) % KMEMS;
  // unsafe check
  if (kmems[j].freelist)
  {
    // acquire lock
    acquire(&kmems[j].lock);
    // double check
    if (kmems[j].freelist)
    {
      r = kmems[j].freelist;
      kmems[j].freelist = r->next;
    }
    release(&kmems[j].lock);
  }
}

测试结果：和 3.3 一样，修改得到的程序不能过 test1，test2、usertests sbrkmuch、usertests 可以通过。进一步优化的效果并不是很明显，tot 的值表现的很随机，在两位数到五位数之间波动。

4 最终优化结果

// Physical memory allocator, for user processes,
// kernel stacks, page-table pages,
// and pipe buffers. Allocates whole 4096-byte pages.

#include "types.h"
#include "param.h"
#include "memlayout.h"
#include "spinlock.h"
#include "riscv.h"
#include "defs.h"

void freerange(void *pa_start, void *pa_end);

extern char end[]; // first address after kernel.
                   // defined by kernel.ld.

int do_rand(uint64 *ctx)
{
  long x = (*ctx % 0x7ffffffe) + 1;
  long hi = x / 127773;
  long lo = x % 127773;
  x = 16807 * lo - 2836 * hi;
  if (x < 0)
    x += 0x7fffffff;
  x--;
  *ctx = x;
  return x;
}

uint64 rand_next[NCPU] = {1};

int randN(void)
{
  return do_rand(&rand_next[cpuid()]);
}

struct run
{
  struct run *next;
};

#define KMEMS 300

struct kmem
{
  struct spinlock lock;
  struct run *freelist;
} kmems[KMEMS];

void kinit()
{
  for (int i = 0; i < KMEMS; i++)
    initlock(&kmems[i].lock, "kmems");

  freerange(end, (void *)PHYSTOP);
}

void freerange(void *pa_start, void *pa_end)
{
  char *p;
  p = (char *)PGROUNDUP((uint64)pa_start);
  for (; p + PGSIZE <= (char *)pa_end; p += PGSIZE)
    kfree(p);
}

// Free the page of physical memory pointed at by v,
// which normally should have been returned by a
// call to kalloc().  (The exception is when
// initializing the allocator; see kinit above.)
void kfree(void *pa)
{
  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;

  int id = randN() % KMEMS;
  acquire(&kmems[id].lock);
  {
    r->next = kmems[id].freelist;
    kmems[id].freelist = r;
  }
  release(&kmems[id].lock);
}

// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
void *
kalloc(void)
{
  struct run *r = (void *)0;

  int id = randN() % KMEMS;
  // unsafe check
  if (kmems[id].freelist)
  {
    // acquire lock
    acquire(&kmems[id].lock);
    // double check
    if (kmems[id].freelist)
    {
      r = kmems[id].freelist;
      kmems[id].freelist = r->next;
    }
    release(&kmems[id].lock);
  }

  // r = null, then steal from all freelist
  int j;
  for (int i = 0; (!r) && (i < KMEMS); i++)
  {
    j = (id + 1 + i) % KMEMS;
    // unsafe check
    if (kmems[j].freelist)
    {
      // acquire lock
      acquire(&kmems[j].lock);
      // double check
      if (kmems[j].freelist)
      {
        r = kmems[j].freelist;
        kmems[j].freelist = r->next;
      }
      release(&kmems[j].lock);
    }
  }

  if (r)
    memset((char *)r, 5, PGSIZE); // fill with junk

  return (void *)r;
}

测试结果：

修改得到的程序不能过 test1，test2、usertests sbrkmuch、usertests 可以通过。进一步优化的效果并不是很明显，tot 的值表现的很随机，在两位数到五位数之间波动。

$ kalloctest
start test1
test1 results:
--- lock kmem/bcache stats
--- top 5 contended locks:
lock: proc: #fetch-and-add 352726 #acquire() 798905
lock: proc: #fetch-and-add 282570 #acquire() 798882
lock: proc: #fetch-and-add 277342 #acquire() 798864
lock: proc: #fetch-and-add 276305 #acquire() 798866
lock: proc: #fetch-and-add 264624 #acquire() 798864
tot= 1875
test1 FAIL
start test2
total free number of pages: 32496 (out of 32768)
.....
test2 OK

usertests 输出太多，略。

5 总结

freelist 和 cpuid 对应的设计是很正确的。不管是 kfree 还是 kalloc，每次都优先从自己的 freelist 开始取或者还，这样减少了很多的锁争用。

kfree、kalloc 随机还和取 free page 的设计是有缺陷的。

通过这一系列测试，说明了 cpuid 对应 freelist 设计的优点。

再返回去看之前的问题：

是不是在 kalloc 和 kfree 的时候足够随机就能避免竞争？
大家的行为都会很随机，那这样竞争的概率不会很小吗？
那么即使有多个 kalloc 和 kfree 同时发生，但是由于他们访问的 freelist 不同，所以不会产生很多锁争用。

在 3.3 中，我们发现过多的 freelist 可能会让遍历的过程变得更漫长，以及更多的锁和锁争用。这是我们不希望的。我们本来希望通过增加 freelist 的数量来使得竞争概率减小，但是最后却造成了更多的锁争用。

大佬指点，从另外的角度分析：

程序分配内存是具有局部性的。这样的话基于 cpuid 对应的做法才具有合理性。
基于 cpuid 的窃取做法是建立在窃取这件事发生概率低之上的，或者说两个进程抢内存的概率较小，这个概率是由实际程序的行为统计来的；在此之上对应 cpuid 的做法可以去除不需要窃取的情况下的锁争用；而散列的做法没法避免这个部分，只是尽量减少了竞争。

6 局部性

解释一下上面用局部性来说明合理性的结论。

6.1 思考实际的过程

基于 cpuid 对应的设计：

init 的时候，通过 free 为每个 CPU 都提供了一个 page 数较为均等的 freelist。

后续在使用的时候，进程（or CPU）申请了很多内存，那么就是先从自己这预分配有一定量 free page 的 freelist 取；之后释放，也是释放到自己的 freelist 中。

那么进一步考虑”连续申请并释放”这个内存使用的局部性。

程序在短时间内的行为模式是倾向于相同的。对于一个短时间内申请了大量内存，然后又释放了大量内存的程序，我们可以期望，他在接下来的时间内，做相同事情的概率很大。

拥有自己的 freelist 这件事就是非常合理的——考虑到局部性，之后仍然是从自己的 freelist 取和还；能满足上一次取和还的 freelist，这一次很大可能能继续满足，即基本上没有竞争的可能（如果不够，那么就窃取，这样最后 freelist 里的 free page 量就更多了，下下一次的行为就更好满足了；当然，在预分配了 freelist 后，窃取的概率也是很低的）。你可以认为这样的设计利用了局部性。

kalloc、kfree 随机设计：

init 的时候，所有的 free page 被较为均匀的分配到 freelist 中，而并不是 CPU 的 “预备” freelist，可以说 CPU 并不预先拥有有一定量 free page 的 freelist 的了。也就是说，进程在申请内存的时候，总是去 kmems[KMEMS] 中去随机的去取；释放内存的时候，总是去 kmems[KMEMS] 中去随机的释放。

进一步，根据局部性，应该为“连续申请并释放”这个事件的再次发生提供便利，但是这种随机的设计却并没有提供着这种便利：不管是第一次，第二次，还是第 N 次，都是在 kmems[KMEMS] 中随机取放——这是很随机的，无记忆性的，没有根据进程之前的行为进行预测或者优化的。你可以认为这样的设计并没有利用局部性。

6.2 从某个称作“局面”的东西去考虑

基于 cpuid 对应的设计：

局面很清楚（因为 freelist 很方便列举）。

例如（仅举例说明，不代表真实情况）：

id	freelist 内 page 数量
0	300
1	356
2	600
3	234
4	360
5	323
6	540
7	233

局面就是各个对应的 freelist 的 page 数量。

从同一个初始局面开始，不同的 CPU 完成一样的行为（申请内存和释放内存），得到的局面是不一样的。并且，不同 CPU 完成这样的行为之后，局面就向着下一次更方便的执行这个行为变化。

kalloc、kfree 随机设计：

freelist 太多，局面不好表示。故局面用概率分布密度函数去描述概括。

例如（仅举例说明，不代表真实情况）：

freelist 内 page 数量	处于该区间的 freelist 占所有 freelist 的百分比
1 - 100	3%
100-200	10%
200 - 300	20%
300 - 400	40%
...	...

随机变量 x 是 freelist 中 page 数量，f(x) 是是这个数量的 freelist 占所有 freelist 的百分比。

$$ P(a<x \le b)=\int_{a}^{b}f(x)\mathrm{d}x $$

从同一个初始局面 $f_0 (x)$ 开始，不同的 CPU 完成一样的行为（申请内存和释放内存），得到的局面是一样的，都变化为 $f_{new} (x)$，对局面的改变是相同的。也就是说这种设计不会被某个特定 CPU 影响，那么自然局面也不会向着方便某个 CPU 去执行行为去变化——并没有这样的趋势。

最后修改：2022 年 11 月 13 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

MIT 6.S081 - Lab Lock - Memory allocator - test

Shirou • 2022 年 10 月 25 日

<h1>MIT 6.S081 - Lab Lock - Memory allocator - test</h1><p>代码传送门：<span class="external-link"><a class="no-external-link" href="https://github.com/xuanhao44/OS_Learn/blob/main/code/lab8/kalloc_test.c" target="_blank"><i data-feather="external-link"></i>OS_Learn/kalloc_test.c at main · xuanhao44/OS_Learn (github.com)</a></span></p><p>【仅包含部分代码，不能运行请自行查看文章补充相关内容】</p><p>本篇是我的测试过程，建议写完第一个 part 再来看。</p><h2>1 某个思路：随机</h2><p><strong>freelist 和 cpuid 一定要对应起来吗？</strong></p><p>既不对应，也不能从一个固定的位置去拿，应该怎么办？只能是随机了。</p><p>同时猜想：是不是在 kalloc 和 kfree 的时候足够随机就能避免竞争？大家的行为都会很随机，那这样竞争的概率不会很小吗？那么即使有多个 kalloc 和 kfree 同时发生，但是由于他们访问的 freelist 不同，所以不会产生很多锁争用。</p><p>在这种情况下，可初步预测：</p><ul><li>开始 init 时，内存页被较均匀的分到了所有 freelist 的中。</li><li>在进程需要 kalloc 时，kalloc.c 从随机的一个 freelist 中为他找到一个 free page。</li><li>在进程需要 kfree 时，kalloc.c 找到随机的一个 freelist 放入进程释放的 page。</li></ul><h2>2 初步考虑随机相关问题</h2><h3>2.1 产生随机数</h3><p>线性同余发生器：给出了产生随机数的例子。发现于 <code>user/grind.c</code>。</p><pre><code class="lang-c">int do_rand(uint64 *ctx)
{
    long x = (*ctx % 0x7ffffffe) + 1;
    long hi = x / 127773;
    long lo = x % 127773;
    x = 16807 * lo - 2836 * hi;
    if (x &lt; 0)
        x += 0x7fffffff;
    x--;
    *ctx = x;
    return x;
}

uint64 rand_next = 1;

int randN(void)
{
    return do_rand(&amp;rand_next);
}</code></pre><h3>2.2 模数取决于 freelist 数量</h3><p>产生的随机数很大，不是拿来直接用的。一般的做法是对其取模。</p><p>那么选什么当模数？模数取决于 freelist 的数量。设置为多少比较好呢？</p><h4>2.2.1 实际运行的 CPU 个数</h4><p>尝试设置为实际运行的 CPU 个数。</p><p>想在 xv6 中获取实际运行的 CPU 个数是困难的，只能从宏导入：</p><p><strong>在 makefile 中添加参数，在 main.c 设置 CPU_NUM 获取，在 kalloc.c 中用 extern 使用。</strong></p><p><code>makefile</code> 中加上：</p><pre><code class="lang-makefile">CFLAGS += -DCPUS=${CPUS}</code></pre><p><code>kernel/main.c</code> 中：（截取部分）</p><pre><code class="lang-c">volatile static int started = 0;

int CPU_NUM = 0;

// start() jumps here in supervisor mode on all CPUs.
void
main()
{
  if(cpuid() == 0){
    consoleinit();
#if defined(LAB_PGTBL) || defined(LAB_LOCK)
    statsinit();
#endif
    printfinit();
    printf(&quot;\n&quot;);
    printf(&quot;xv6 kernel is booting\n&quot;);
    #if defined(CPUS)
      CPU_NUM = CPUS;
      printf(&quot;CPU_NUM = %d\n&quot;, CPU_NUM);
    #endif
    printf(&quot;\n&quot;);</code></pre><p><code>kernel/kalloc.c</code> 中：</p><pre><code class="lang-c">extern int CPU_NUM; // from main.c
                    // defined by makefile</code></pre><h4>2.2.2 设置为较大的数</h4><p>为什么 freelist 的数量一定要和实际 CPU 数量挂钩呢？这不太合理。我们完全可以设置为一个较大的数。</p><p>在下面的实验中，我们将设置为 300。</p><pre><code class="lang-c">#define KMEMS 300

struct kmem
{
  struct spinlock lock;
  struct run *freelist;
} kmems[KMEMS];</code></pre><p><em>实际上设置多少挺玄学的，要考虑到很多问题。接下来会提到一部分，但也不完全。</em></p><p>经测试发现：</p><ul><li>在 CPU 数为 8 的情况下，KMEMS 高于某个值后，在编译 xv6 时就会 panic，该值为 315；</li><li>成功编译的情况下，KMEMS 高于某个值后，测试程序 <code>usertests sbrkmuch</code> 也会 panic，该值为 310；</li><li>上限值 315 和 310 与 CPU 数无关；不保证该值是准确值，不保证一直有效，仅供参考。</li><li><code>kalloctest</code> test1 如果输出太多会崩掉，故去掉大量输出，下面是原因和调整方法。</li></ul><p><code>user/kalloctest.c</code> 片段：</p><pre><code class="lang-c">#define NCHILD 2
#define N 100000
#define SZ 4096

void test1(void);
void test2(void);
char buf[SZ];

int
main(int argc, char *argv[])
{
  test1();
  test2();
  exit(0);
}

int ntas(int print)
{
  int n;
  char *c;

if (statistics(buf, SZ) &lt;= 0) {
    fprintf(2, &quot;ntas: no stats\n&quot;);
  }
  c = strchr(buf, '=');
  n = atoi(c+2);
  if(print)
    printf(&quot;%s&quot;, buf);
  return n;
}</code></pre><p>注意到 SZ 只有 4096，输出多起来就会出错。</p><p>于是把 <code>kernel/spinlock.c:statslock()</code> 的一个循环里输出 <code>kmem.lock</code> 的部分注释掉。</p><pre><code class="lang-c">for(int i = 0; i &lt; NLOCK; i++) {
    if(locks[i] == 0)
      break;
    if(strncmp(locks[i]-&gt;name, &quot;bcache&quot;, strlen(&quot;bcache&quot;)) == 0 ||
       strncmp(locks[i]-&gt;name, &quot;kmem&quot;, strlen(&quot;kmem&quot;)) == 0) {
      tot += locks[i]-&gt;nts;
      // n += snprint_lock(buf +n, sz-n, locks[i]);
    }
  }</code></pre><p>这样输出就少了很多，当然 tot 的统计还是正常的，所以不影响最后的判断。</p><h2>3 从一个错误百出的程序开始</h2><p>让我们以这个程序为基础，一步步开始 ”优化“ 吧。</p><pre><code class="lang-c">// Physical memory allocator, for user processes,
// kernel stacks, page-table pages,
// and pipe buffers. Allocates whole 4096-byte pages.

#include &quot;types.h&quot;
#include &quot;param.h&quot;
#include &quot;memlayout.h&quot;
#include &quot;spinlock.h&quot;
#include &quot;riscv.h&quot;
#include &quot;defs.h&quot;

void freerange(void *pa_start, void *pa_end);

extern char end[]; // first address after kernel.
                   // defined by kernel.ld.

int do_rand(uint64 *ctx)
{
  long x = (*ctx % 0x7ffffffe) + 1;
  long hi = x / 127773;
  long lo = x % 127773;
  x = 16807 * lo - 2836 * hi;
  if (x &lt; 0)
    x += 0x7fffffff;
  x--;
  *ctx = x;
  return x;
}

uint64 rand_next = 1;

int randN(void)
{
  return do_rand(&amp;rand_next);
}

struct run
{
  struct run *next;
};

#define KMEMS 300

struct kmem
{
  struct spinlock lock;
  struct run *freelist;
} kmems[KMEMS];

void kinit()
{
  for (int i = 0; i &lt; KMEMS; i++)
    initlock(&amp;kmems[i].lock, &quot;kmems&quot;);

freerange(end, (void *)PHYSTOP);
}

void freerange(void *pa_start, void *pa_end)
{
  char *p;
  p = (char *)PGROUNDUP((uint64)pa_start);
  for (; p + PGSIZE &lt;= (char *)pa_end; p += PGSIZE)
    kfree(p);
}

// Free the page of physical memory pointed at by v,
// which normally should have been returned by a
// call to kalloc().  (The exception is when
// initializing the allocator; see kinit above.)
void kfree(void *pa)
{
  struct run *r;

if (((uint64)pa % PGSIZE) != 0 || (char *)pa &lt; end || (uint64)pa &gt;= PHYSTOP)
    panic(&quot;kfree&quot;);

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

r = (struct run *)pa;

int id = randN() % KMEMS;
  acquire(&amp;kmems[id].lock);
  {
    r-&gt;next = kmems[id].freelist;
    kmems[id].freelist = r;
  }
  release(&amp;kmems[id].lock);
}

// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
void *
kalloc(void)
{
  struct run *r;
  int id;
  do
  {
    id = randN() % KMEMS;
    acquire(&amp;kmems[id].lock);
    {
      r = kmems[id].freelist;
      if (r)
        kmems[id].freelist = r-&gt;next;
    }
    release(&amp;kmems[id].lock);
  } while (!r);

if (r)
    memset((char *)r, 5, PGSIZE); // fill with junk

return (void *)r;
}</code></pre><p>测试结果：<code>kalloctest</code> test1 没过，test2 根本无法开始；<code>usertests sbrkmuch</code>、<code>usertests</code> 也都卡住了！</p><h3>3.1 不可完全随机的 kalloc</h3><p>错误也许是显然的。</p><pre><code class="lang-c">struct run *r;
int id;
do
{
  id = randN() % KMEMS;
  acquire(&amp;kmems[id].lock);
  {
    r = kmems[id].freelist;
    if (r)
      kmems[id].freelist = r-&gt;next;
  }
  release(&amp;kmems[id].lock);
} while (!r);</code></pre><p>假设一种情况：使用的内存过多，各个 freelist 都没有多少 free page 了。</p><p>对应到这段代码，我们只是随机的选取了一个 freelist，然后去取它的 free page，如果没有的话就再次随机的选取一个 freelist。</p><p>然而各个 freelist 都没有多少 free page 了，故而随机选取一次，能找到 free page 的概率是很低的。</p><p>从整体上说，随着分配回收 free page 的进行，如果进程申请的内存比释放的 free page 多，所有 freelist 的 free page 是在不断减少的，随机选取一次，能找到 free page 的概率会降低；如果有 N 个 freelist 没有 free page 了，那么随机选取一次，能找到 free page 的概率就是 $(1 - N/{KMEMS})$。</p><p>既然不能完全随机，那么我们改变策略：</p><p>先随机选取一次；如果没有得到 free page，就遍历所有 freelist 去寻找 free page。</p><pre><code class="lang-c">void *
kalloc(void)
{
  struct run *r;

int id = randN()  % KMEMS;
  acquire(&amp;kmems[id].lock);
  {
    r = kmems[id].freelist;
    if (r)
      kmems[id].freelist = r-&gt;next;
  }
  release(&amp;kmems[id].lock);

// r = null, then steal from all freelist
  for (int i = 0; (!r) &amp;&amp; (i &lt; KMEMS); i++)
  {
    if (i == id)
      continue;

acquire(&amp;kmems[i].lock);
    {
      r = kmems[i].freelist;
      if (r)
        kmems[i].freelist = r-&gt;next;
    }
    release(&amp;kmems[i].lock);
  }

if (r)
    memset((char *)r, 5, PGSIZE); // fill with junk

return (void *)r;
}</code></pre><p>测试结果：修改得到的程序虽然不能过 test1，但是 test2、<code>usertests sbrkmuch</code>、<code>usertests</code> 可以通过。</p><h3>3.2 随机是否起效</h3><p>实际上，上面程序生成随机数 <code>randN() % KMEMS</code> 并没有起到应有的效果。进程共享着 <code>uint64 rand_next</code>，也就是说在多数时候，同时运行的 CPU 使用着相同的 <code>rand_next</code>，那么对于线性同余发生器来说得到的值就是相同的——这完全不是我们想要的。我们希望同时运行的 CPU 通过随机达成减少竞争，而这个想法根本没有被实现。</p><p>改进的方法是：为每一个 CPU 设置 <code>rand_next</code>，每一个 CPU 在获取随机数时需要使用自己的 <code>rand_next</code>。</p><pre><code class="lang-c">uint64 rand_next[NCPU] = {1};

int randN(void)
{
  return do_rand(&amp;rand_next[cpuid()]);
}</code></pre><p><em>考虑一下为什么没有像平常那样关闭和打开中断：使用 cpuid 时，我们不在意 CPU 是否切换——这对随机数的生成并没有实质的影响。</em></p><p>测试结果：修改得到的程序不能过 test1，test2、<code>usertests sbrkmuch</code>、<code>usertests</code> 可以通过。但是 test1 的 tot 值明显的变小了很多。就是从上万到了两位数，这是个很大的进步！</p><p><em>tot 的值表现的很随机，在两位数到五位数之间波动。但是能到两位数了。</em></p><h3>3.3 考虑锁：double check</h3><p>一个可能出现的情况是所有 freelist 中剩余的 free page 不多。在这种情况下，很多加锁的步骤都是无效的，开销很大，且增加了很多锁争用。</p><p><strong>采用 “不安全 check + 加锁 double check” 的处理模式：利用某些可以允许的不安全来换取缩小的锁范围，然后再使用额外的手段保证正确性。</strong></p><pre><code class="lang-c">void *
kalloc(void)
{
  struct run *r = (void *)0;

int id = randN() % KMEMS;
  // unsafe check
  if (kmems[id].freelist)
  {
    // acquire lock
    acquire(&amp;kmems[id].lock);
    // double check
    if (kmems[id].freelist)
    {
      r = kmems[id].freelist;
      kmems[id].freelist = r-&gt;next;
    }
    release(&amp;kmems[id].lock);
  }

// r = null, then steal from all freelist
  for (int i = 0; (!r) &amp;&amp; (i &lt; KMEMS); i++)
  {
    if (i == id)
      continue;

if (kmems[i].freelist)
    {
      // acquire lock
      acquire(&amp;kmems[i].lock);
      // double check
      if (kmems[i].freelist)
      {
        r = kmems[i].freelist;
        kmems[i].freelist = r-&gt;next;
      }
      release(&amp;kmems[i].lock);
    }
  }

if (r)
    memset((char *)r, 5, PGSIZE); // fill with junk

return (void *)r;
}</code></pre><p>测试结果：修改得到的程序不能过 test1，test2、<code>usertests sbrkmuch</code>、<code>usertests</code> 可以通过。进一步优化的效果并不是很明显，tot 的值表现的很随机，在两位数到五位数之间波动。</p><h3>3.4 考虑更随机的遍历</h3><p>每次都从 0 开始不够随机，我们可以从 id + 1 开始遍历，充分利用了上面的随机数。</p><pre><code class="lang-c">int j;
for (int i = 0; (!r) &amp;&amp; (i &lt; KMEMS); i++)
{
  j = (id + 1 + i) % KMEMS;
  // unsafe check
  if (kmems[j].freelist)
  {
    // acquire lock
    acquire(&amp;kmems[j].lock);
    // double check
    if (kmems[j].freelist)
    {
      r = kmems[j].freelist;
      kmems[j].freelist = r-&gt;next;
    }
    release(&amp;kmems[j].lock);
  }
}</code></pre><p>测试结果：和 3.3 一样，修改得到的程序不能过 test1，test2、<code>usertests sbrkmuch</code>、<code>usertests</code> 可以通过。进一步优化的效果并不是很明显，tot 的值表现的很随机，在两位数到五位数之间波动。</p><h3>4 最终优化结果</h3><pre><code class="lang-c">// Physical memory allocator, for user processes,
// kernel stacks, page-table pages,
// and pipe buffers. Allocates whole 4096-byte pages.

#include &quot;types.h&quot;
#include &quot;param.h&quot;
#include &quot;memlayout.h&quot;
#include &quot;spinlock.h&quot;
#include &quot;riscv.h&quot;
#include &quot;defs.h&quot;

void freerange(void *pa_start, void *pa_end);

extern char end[]; // first address after kernel.
                   // defined by kernel.ld.

uint64 rand_next[NCPU] = {1};

int randN(void)
{
  return do_rand(&amp;rand_next[cpuid()]);
}

struct run
{
  struct run *next;
};

#define KMEMS 300

struct kmem
{
  struct spinlock lock;
  struct run *freelist;
} kmems[KMEMS];

void kinit()
{
  for (int i = 0; i &lt; KMEMS; i++)
    initlock(&amp;kmems[i].lock, &quot;kmems&quot;);

freerange(end, (void *)PHYSTOP);
}

void freerange(void *pa_start, void *pa_end)
{
  char *p;
  p = (char *)PGROUNDUP((uint64)pa_start);
  for (; p + PGSIZE &lt;= (char *)pa_end; p += PGSIZE)
    kfree(p);
}

if (((uint64)pa % PGSIZE) != 0 || (char *)pa &lt; end || (uint64)pa &gt;= PHYSTOP)
    panic(&quot;kfree&quot;);

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

r = (struct run *)pa;

int id = randN() % KMEMS;
  acquire(&amp;kmems[id].lock);
  {
    r-&gt;next = kmems[id].freelist;
    kmems[id].freelist = r;
  }
  release(&amp;kmems[id].lock);
}

// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
void *
kalloc(void)
{
  struct run *r = (void *)0;

// r = null, then steal from all freelist
  int j;
  for (int i = 0; (!r) &amp;&amp; (i &lt; KMEMS); i++)
  {
    j = (id + 1 + i) % KMEMS;
    // unsafe check
    if (kmems[j].freelist)
    {
      // acquire lock
      acquire(&amp;kmems[j].lock);
      // double check
      if (kmems[j].freelist)
      {
        r = kmems[j].freelist;
        kmems[j].freelist = r-&gt;next;
      }
      release(&amp;kmems[j].lock);
    }
  }

if (r)
    memset((char *)r, 5, PGSIZE); // fill with junk

return (void *)r;
}</code></pre><p>测试结果：</p><p>修改得到的程序不能过 test1，test2、<code>usertests sbrkmuch</code>、<code>usertests</code> 可以通过。进一步优化的效果并不是很明显，tot 的值表现的很随机，在两位数到五位数之间波动。</p><pre><code class="lang-shell">$ kalloctest
start test1
test1 results:
--- lock kmem/bcache stats
--- top 5 contended locks:
lock: proc: #fetch-and-add 352726 #acquire() 798905
lock: proc: #fetch-and-add 282570 #acquire() 798882
lock: proc: #fetch-and-add 277342 #acquire() 798864
lock: proc: #fetch-and-add 276305 #acquire() 798866
lock: proc: #fetch-and-add 264624 #acquire() 798864
tot= 1875
test1 FAIL
start test2
total free number of pages: 32496 (out of 32768)
.....
test2 OK</code></pre><p><code>usertests</code> 输出太多，略。</p><h2>5 总结</h2><p>freelist 和 cpuid 对应的设计是很正确的。不管是 kfree 还是 kalloc，每次都优先从自己的 freelist 开始取或者还，这样减少了很多的锁争用。</p><p>kfree、kalloc 随机还和取 free page 的设计是有缺陷的。</p><p>通过这一系列测试，说明了 cpuid 对应 freelist 设计的优点。</p><p>再返回去看之前的问题：</p><blockquote><p>是不是在 kalloc 和 kfree 的时候足够随机就能避免竞争？</p><p>大家的行为都会很随机，那这样竞争的概率不会很小吗？</p><p>那么即使有多个 kalloc 和 kfree 同时发生，但是由于他们访问的 freelist 不同，所以不会产生很多锁争用。</p></blockquote><p>在 3.3 中，我们发现过多的 freelist 可能会让遍历的过程变得更漫长，以及更多的锁和锁争用。这是我们不希望的。我们本来希望通过增加 freelist 的数量来使得竞争概率减小，但是最后却造成了更多的锁争用。</p><p>大佬指点，从另外的角度分析：</p><ul><li>程序分配内存是具有局部性的。这样的话基于 cpuid 对应的做法才具有合理性。</li><li>基于 cpuid 的窃取做法是建立在窃取这件事发生概率低之上的，或者说两个进程抢内存的概率较小，这个概率是由实际程序的行为统计来的；在此之上对应 cpuid 的做法可以去除不需要窃取的情况下的锁争用；而散列的做法没法避免这个部分，只是尽量减少了竞争。</li></ul><h2>6 局部性</h2><p>解释一下上面用局部性来说明合理性的结论。</p><h3>6.1 思考实际的过程</h3><p>基于 cpuid 对应的设计：</p><p>init 的时候，通过 free 为每个 CPU 都提供了一个 page 数较为均等的 freelist。</p><p>后续在使用的时候，进程（or CPU）申请了很多内存，那么就是先从自己这预分配有一定量 free page 的 freelist 取；之后释放，也是释放到自己的 freelist 中。</p><p>那么进一步考虑”连续申请并释放”这个内存使用的<strong>局部性</strong>。</p><blockquote>程序在短时间内的行为模式是倾向于相同的。对于一个短时间内申请了大量内存，然后又释放了大量内存的程序，我们可以期望，他在接下来的时间内，做相同事情的概率很大。</blockquote><p>拥有自己的 freelist 这件事就是非常合理的——考虑到局部性，之后仍然是从自己的 freelist 取和还；能满足上一次取和还的 freelist，这一次很大可能能继续满足，即基本上没有竞争的可能（如果不够，那么就窃取，这样最后 freelist 里的 free page 量就更多了，下下一次的行为就更好满足了；当然，在预分配了 freelist 后，窃取的概率也是很低的）。<strong>你可以认为这样的设计利用了局部性。</strong></p><p>kalloc、kfree 随机设计：</p><p>init 的时候，所有的 free page 被较为均匀的分配到 freelist 中，而并不是 CPU 的 “预备” freelist，可以说 CPU 并不预先拥有有一定量 free page 的 freelist 的了。也就是说，进程在申请内存的时候，总是去 <code>kmems[KMEMS]</code> 中去随机的去取；释放内存的时候，总是去 <code>kmems[KMEMS]</code> 中去随机的释放。</p><p>进一步，根据局部性，应该为“连续申请并释放”这个事件的再次发生提供便利，但是这种随机的设计却并没有提供着这种便利：不管是第一次，第二次，还是第 N 次，都是在 <code>kmems[KMEMS]</code> 中随机取放——这是很随机的，无记忆性的，没有根据进程之前的行为进行预测或者优化的。<strong>你可以认为这样的设计并没有利用局部性。</strong></p><h3>6.2 从某个称作“局面”的东西去考虑</h3><p>基于 cpuid 对应的设计：</p><p>局面很清楚（因为 freelist 很方便列举）。</p><p>例如（仅举例说明，不代表真实情况）：</p><table><thead><tr><th align="center">id</th><th align="center">freelist 内 page 数量</th></tr></thead><tbody><tr><td align="center">0</td><td align="center">300</td></tr><tr><td align="center">1</td><td align="center">356</td></tr><tr><td align="center">2</td><td align="center">600</td></tr><tr><td align="center">3</td><td align="center">234</td></tr><tr><td align="center">4</td><td align="center">360</td></tr><tr><td align="center">5</td><td align="center">323</td></tr><tr><td align="center">6</td><td align="center">540</td></tr><tr><td align="center">7</td><td align="center">233</td></tr></tbody></table><p>局面就是各个对应的 freelist 的 page 数量。</p><p>从同一个初始局面开始，不同的 CPU 完成一样的行为（申请内存和释放内存）<strong>，得到的局面是不一样的</strong>。并且，不同 CPU 完成这样的行为之后，<strong>局面就向着下一次更方便的执行这个行为变化</strong>。</p><p>kalloc、kfree 随机设计：</p><p>freelist 太多，局面不好表示。故局面用概率分布密度函数去描述概括。</p><p>例如（仅举例说明，不代表真实情况）：</p><table><thead><tr><th align="center">freelist 内 page 数量</th><th align="center">处于该区间的 freelist 占所有 freelist 的百分比</th></tr></thead><tbody><tr><td align="center">1 - 100</td><td align="center">3%</td></tr><tr><td align="center">100-200</td><td align="center">10%</td></tr><tr><td align="center">200 - 300</td><td align="center">20%</td></tr><tr><td align="center">300 - 400</td><td align="center">40%</td></tr><tr><td align="center">...</td><td align="center">...</td></tr></tbody></table><p>随机变量 x 是 freelist 中 page 数量，f(x) 是是这个数量的 freelist 占所有 freelist 的百分比。</p><p>$$
P(a&lt;x \le b)=\int_{a}^{b}f(x)\mathrm{d}x
$$</p><p>从同一个初始局面 $f_0 (x)$ 开始，不同的 CPU 完成一样的行为（申请内存和释放内存），<strong>得到的局面是一样的，都变化为 $f_{new} (x)$，对局面的改变是相同的</strong>。也就是说这种设计不会被某个特定 CPU 影响，那么自然局面也不会向着方便某个 CPU 去执行行为去变化——并没有这样的趋势。</p>

MIT 6.S081 - Lab Lock - Memory allocator - test

1 某个思路：随机

2 初步考虑随机相关问题

2.1 产生随机数

2.2 模数取决于 freelist 数量

2.2.1 实际运行的 CPU 个数

2.2.2 设置为较大的数

3 从一个错误百出的程序开始

3.1 不可完全随机的 kalloc

3.2 随机是否起效

3.3 考虑锁：double check

3.4 考虑更随机的遍历

4 最终优化结果

5 总结

6 局部性

6.1 思考实际的过程

6.2 从某个称作“局面”的东西去考虑

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

MIT 6.S081 - Lab Lock - Memory allocator - test

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款