本文源码文件是kernel/kalloc.c，理解的内容为：全局变量：end[]、结构体：run&kmem、kfree函数、freerange函数、kinit函数、kalloc函数

00_前言

它是物理内存分配器，主要功能是管理物理内存的分配和释放。

01_全局变量：end[]

1.作用

标明了自由物理内存的开始位置

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

02_结构体：run & kmem

1.作用

用于管理物理内存的分配和释放。它们共同构成了一个简单的自由链表（free list），用于跟踪系统中的空闲物理内存页。

2.代码
// run结构体就是一个指向自身的指针，用于指向下一个空闲页表开始位置
struct run {
  struct run *next;
};

// 管理物理内存的结构
// 有一把锁lock保证访问时的互斥性
// 以及一个指向
struct {
  struct spinlock lock;
  struct run *freelist;
} kmem;
3.逻辑
(1)run

假设有三块空闲的物理内存页，分别位于内存地址 0x1000, 0x2000, 和 0x3000。这些内存页可以用 struct run 链表来表示：

#define PAGE1_ADDR 0x1000
#define PAGE2_ADDR 0x2000
#define PAGE3_ADDR 0x3000

struct run *page1 = (struct run *)PAGE1_ADDR;
struct run *page2 = (struct run *)PAGE2_ADDR;
struct run *page3 = (struct run *)PAGE3_ADDR;

// 链接这些结构体
page1->next = page2;
page2->next = page3;
page3->next = 0;  // 最后一个节点，指向 NULL
  • page1 表示物理地址 0x1000 的空闲页，它的 next 指针指向 page2，表示下一块空闲页在 0x2000。
  • page2 的 next 指针指向 page3，表示下一块空闲页在 0x3000。
  • page3 的 next 为 0，表示这是最后一块空闲页。
(2)kmem
struct {
  struct spinlock lock;
  struct run *freelist;
} kmem;

  • 作用：kmem 是内存管理的核心结构体，用来管理整个系统的空闲内存页。

  • 成员：

    • lock：一把自旋锁(spinlock)，用于确保在多处理器环境中对空闲内存链表的访问是互斥的。这意味着在一个时刻，只有一个 CPU 或进程可以修改空闲内存链表，防止多个进程同时修改链表导致数据不一致或内存泄漏。
    • freelist：指向第一个空闲内存页的 struct run 节点。通过这个指针，内存管理系统可以访问整个空闲页链表。

  • 作用过程：

    • 初始化阶段：当操作系统启动时，kmem.freelist 被初始化为指向第一个空闲页（例如 page1），这个指针指向一个 run 结构体。

    假设系统初始化时有三块空闲页，那么 kmem.freelist 将指向 page1，而 page1 的 next 指针将指向 page2，page2 的 next 指向 page3，形成一个链表结构。

    kmem.freelist = &page1;

    • 分配内存：当内核需要分配一页物理内存时，它会获取 kmem.lock 锁，确保其他进程不会同时修改链表。然后，它会取出 kmem.freelist 指向的页，将 kmem.freelist 更新为下一个空闲页（page1.next）。这个操作确保内核获取了一个空闲页，并将其从链表中移除。

    • 释放内存：当内核不再需要某个物理内存页时，它会调用释放函数，把该页重新插入 kmem.freelist 链表中。插入操作同样需要先获取 kmem.lock 锁以确保互斥。

03_kfree函数

1.作用

kfree 函数的主要作用是将一个已经分配的物理内存页（由 pa 指针指向）归还到内存管理器的空闲链表中。这个函数通常用于释放通过 kalloc 函数分配的内存页，以便其他部分可以重新使用这些内存。

2.代码
void kfree(void *pa)
{
  struct run *r;

  // 1. 检查内存页的有效性
  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");

  // 2. 将内存填充无用数据（防止悬空引用）
  memset(pa, 1, PGSIZE);

  // 3. 将 pa 转换为 struct run* 类型
  r = (struct run*)pa;

  // 4. 将这个页插入到空闲内存链表的头部
  acquire(&kmem.lock);
  r->next = kmem.freelist;
  kmem.freelist = r;
  release(&kmem.lock);
}
3.逻辑
(1)检查内存页的有效性
if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
  panic("kfree");
  • 页对齐检查：((uint64)pa % PGSIZE) != 0 检查指针 pa 是否指向一个页对齐的地址。PGSIZE 是页的大小（通常为 4096 字节），页对齐意味着地址应该是 PGSIZE 的倍数。
  • 地址范围检查：(char*)pa < end || (uint64)pa >= PHYSTOP 确保 pa 指向的地址在有效的物理内存范围内。
    • end 通常是内核加载结束的位置，pa 不能小于这个地址。
    • PHYSTOP 是物理内存的上限，pa 不能大于或等于这个值。
(2)填充无用数据（防止悬空引用）
memset(pa, 1, PGSIZE);
  • 这一步将内存页 pa 填充为全 1 的数据。这样做的目的是防止在内存释放后，其他代码仍然错误地引用该内存。如果有代码错误地访问了已释放的内存，填充的无用数据会导致程序行为异常，进而暴露出错误。
(3)转换为 struct run* 类型
r = (struct run*)pa;
  • r 是一个 struct run 类型的指针，它指向 pa 所代表的物理页。struct run 结构体被用作空闲内存页的链表节点，因此 pa 现在被视为链表中的一个节点。
(4) 插入到空闲链表中
acquire(&kmem.lock);
r->next = kmem.freelist;
kmem.freelist = r;
release(&kmem.lock);
  • 加锁：通过 acquire(&kmem.lock) 获取锁，以确保在多核或多线程环境中，只有一个线程可以修改空闲链表。这防止了竞态条件和数据损坏。
  • 头插法插入链表：将当前物理页 r 插入到空闲链表的头部。具体做法是将 r->next 指向当前的空闲链表头 kmem.freelist，然后将 kmem.freelist 更新为 r，即新释放的页。
  • 释放锁：通过 release(&kmem.lock) 释放锁，允许其他线程访问链表。

04_freerange函数

1.作用

freerange 函数用于操作系统启动时初始化物理内存管理器。它会将从 pa_start 到 pa_end 之间的物理内存页面释放到空闲页面链表中。例如，xv6 操作系统在启动时会调用 freerange 将内核之外的物理内存标记为空闲，使得这些内存可以被用户进程或内核模块动态分配。

它通过将指定范围内的内存页面逐页释放回到内存管理器的空闲列表中，使得这些页面能够被后续的内存分配请求使用。

2.代码
void freerange(void *pa_start, void *pa_end)
{
  char *p;

  // 向上对齐起始地址，确保释放的是完整的页
  p = (char*)PGROUNDUP((uint64)pa_start);

  // 逐页释放内存，直到pa_end
  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE)
    kfree(p);
}
3.逻辑
(1)对齐起始地址：
p = (char*)PGROUNDUP((uint64)pa_start);
  • PGROUNDUP 是一个宏，用于将地址向上对齐到页面大小（PGSIZE）的倍数。
  • 假设 PGSIZE 是 4096 字节，如果 pa_start 是 0x1003，PGROUNDUP 将其对齐到 0x2000。这样可以确保从一个完整的页面开始释放内存，而不会错误地释放部分页面。
(2)逐页释放内存：
for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE)
  kfree(p);
  • 这是一个循环，从对齐后的 p 地址开始，每次递增 PGSIZE（通常为 4KB）来遍历指定的内存范围。
  • 每次循环调用 kfree(p) 来释放当前页面，并将其加入到空闲页面链表中。
  • 终止条件 p + PGSIZE <= (char*)pa_end 确保在到达或超过 pa_end 时停止循环。这避免了释放超出指定范围的内存。
4.示例

假设在操作系统启动时，内核已经占用了从 0x0 到 0x200000 的物理内存（含代码、数据、BSS 段等），而系统有 256MB 的内存可用。此时，freerange 函数会被调用来释放内核之外的物理内存，例如：

freerange((void*)0x200000, (void*)0x10000000); // 释放从0x200000到0x10000000（256MB）之间的内存

这段代码的作用是将从 0x200000（内核结束地址）到 0x10000000（256MB 结束地址）的所有页面释放，使这些内存可以被内存管理器使用。

05_kinit函数

1.作用

kinit() 函数在操作系统启动时被调用，负责初始化物理内存管理器。它将系统中的物理内存划分为内核使用的部分和可供分配的部分：

  • 内核使用的内存在 end 之前，这部分内存不会被释放。
  • 从 end 到 PHYSTOP 的内存则被标记为空闲，加入到空闲内存链表 kmem.freelist 中。
2.代码
void kinit()
{
  // 初始化锁，用于保护空闲内存链表的并发访问
  initlock(&kmem.lock, "kmem");

  // 释放从 `end` 到 `PHYSTOP` 之间的所有物理内存页面
  // 将这些页面加入到空闲链表 `freelist` 中
  freerange(end, (void*)PHYSTOP);
}
3.逻辑
(1)初始化锁 (initlock)：
initlock(&kmem.lock, "kmem");
  • kmem.lock 是一个自旋锁（spinlock），它用于保护 kmem.freelist 链表的并发访问。因为内存分配和释放可能在多核处理器上并行执行，所以需要用锁来确保在访问或修改空闲链表时，不会发生数据竞争或其他同步问题。
  • initlock 函数用于初始化这把锁，并给它一个名字 "kmem"，用于调试和日志目的。
(2)释放从 end 到 PHYSTOP 之间的内存 (freerange)：
freerange(end, (void*)PHYSTOP);
  • end 是一个指向内核结束位置的指针，这意味着内核代码、数据段、BSS 段等都已经占用了从 0x0 到 end 之间的内存。
  • PHYSTOP 通常定义为物理内存的上限，它表示系统中物理内存的终止地址。
  • freerange(end, (void*)PHYSTOP); 函数的作用是将从 end 到 PHYSTOP 之间的所有物理内存页面标记为空闲，并将这些页面加入到 kmem.freelist 链表中。

操作系统将 end 之后的所有物理内存页面（即不被内核占用的部分）都回收到空闲链表中，供操作系统动态分配给用户进程或内核模块使用。

4.示例

假设系统内核占用了从 0x0 到 0x200000 的物理内存，而系统总共有 256MB（0x10000000）的物理内存。（注意：xv6直接假定内存只有128MB）那么：

  • end 可能是 0x200000。
  • PHYSTOP 定义为 0x10000000。

调用 freerange(end, (void*)PHYSTOP); 将释放从 0x200000 到 0x10000000 的所有物理内存，将这些内存加入到空闲链表中，使得内核可以通过 kalloc() 分配这些页面给用户进程或内核使用。

06_kalloc函数

1.作用

kalloc 函数是 xv6 操作系统中的内存分配器，它负责分配一个大小为 4096 字节（即一页）的物理内存。

当系统或进程需要一块新的物理内存时，可以调用 kalloc 来获取一个空闲的物理页。

2.代码
void *kalloc(void)
{
  struct run *r;

  // 1. 加锁以保护空闲链表的操作
  acquire(&kmem.lock);

  // 2. 从空闲链表中取出第一个空闲页
  r = kmem.freelist;
  if(r)
    kmem.freelist = r->next;  // 将链表头指针移动到下一个节点

  // 3. 解锁
  release(&kmem.lock);

  // 4. 如果分配成功（r不为空），则用随机数据填充该页面
  if(r)
    memset((char*)r, 5, PGSIZE); // 用 5 填充整个页面

  // 5. 返回指向分配的页面的指针
  return (void*)r;
}
3.逻辑
(1)加锁保护空闲链表：
acquire(&kmem.lock);

由于空闲链表 kmem.freelist 可能在多核环境或多线程中被并发访问，acquire(&kmem.lock) 函数用于获取锁，从而确保在操作链表时不会发生竞争条件或数据损坏。

(2)取出链表头的第一个节点：
r = kmem.freelist;
if(r)
  kmem.freelist = r->next;
  • kmem.freelist 指向空闲物理页面链表的头部。r = kmem.freelist 将第一个空闲页面取出，kmem.freelist = r->next 将链表头移动到下一个空闲页面。
  • 如果链表为空（即 r 为 NULL），意味着没有可用的物理页面，这时 kalloc 将返回 NULL，表示分配失败。
(3)解锁：
release(&kmem.lock);
  • 在完成对链表的操作后，release(&kmem.lock) 函数用于释放锁，从而允许其他线程或 CPU 核心访问空闲链表。
(4)填充页面并返回：
if(r)
  memset((char*)r, 5, PGSIZE);
return (void*)r;
  • 如果 r 不为 NULL，表示成功分配了一个物理页面。memset((char*)r, 5, PGSIZE) 会将该页面的所有字节填充为 5，这一步的目的是将页面填满垃圾数据，以便在错误的引用或使用未初始化的内存时更容易发现问题。
  • 最后，函数返回指向这个物理页面的指针。
4.示例

假设操作系统需要为一个新的进程分配一个堆栈空间，可能会调用 kalloc 函数：

void *stack = kalloc();
if(stack == NULL) {
  // 处理内存分配失败的情况
} else {
  // 使用分配的内存
}

在这个示例中，如果 kalloc 返回 NULL，表示系统中没有可用的空闲物理内存页，系统必须处理这个情况（例如通过释放其他资源或返回错误）。

踏上取经路，比抵达灵山更重要