Lab3 | 海苔脆的博客

伙伴系统

buddy_system.py

class buddy_system:
 
    def __init__(self, total_size, min_size):
        if (total_size & (total_size - 1)) != 0 or total_size == 0:
            raise ValueError("total_size must be a power of two.")
        self.total_size = total_size 
        self.min_size = min_size
        self.free_blocks = {total_size: [0]} #空闲的空间
        self.allocated_blocks = {} #已经分配的空间
        self.waiting_queue = []  # 等待队列，存储(process_id, size)元组

    #分配内存
    def allocate(self, process_id, size):
        if process_id in self.allocated_blocks:
            raise ValueError(f"Process ID {process_id} already exists")
            
        required_size = self._calculate_block_size(size)
        found_size = None
        # 查找最小可用块
        for s in sorted(self.free_blocks.keys()):
            if s >= required_size and self.free_blocks[s]:
                found_size = s
                break
        
        # 如果没有足够的内存，加入等待队列
        if not found_size:
            self.waiting_queue.append((process_id, size))
            return False  # 返回False表示请求进入等待状态
        
        # 获取相应地址起始点
        addr = self.free_blocks[found_size].pop(0)
        # 如果没有空闲块则删除
        if not self.free_blocks[found_size]:
            del self.free_blocks[found_size]

        # 分割块直到达到所需大小
        current_size = found_size
        current_addr = addr
        while current_size > required_size:
            current_size //= 2
            buddy_addr = current_addr + current_size
            if current_size not in self.free_blocks:
                self.free_blocks[current_size] = []
            self.free_blocks[current_size].append(buddy_addr)
        
        self.allocated_blocks[process_id] = (current_addr, current_size)
        return True  # 返回True表示分配成功

    #计算需要的块大小
    def _calculate_block_size(self, size):
        block_size = 1
        while block_size < size:
            block_size *= 2
        return max(block_size, self.min_size)

    #释放内存
    def free(self, process_id):
        # 检查进程是否存在
        if process_id not in self.allocated_blocks:
            raise ValueError("Process ID not found")
        # 获取块的地址和大小
        addr, size = self.allocated_blocks.pop(process_id)
        # 将块重新加入空闲列表
        if size not in self.free_blocks:
            self.free_blocks[size] = []
        self.free_blocks[size].append(addr)
        # 合并伙伴块
        current_size = size
        current_addr = addr
        while current_size < self.total_size:
            buddy_addr = current_addr ^ current_size #找到伙伴块的地址
            if current_size not in self.free_blocks or buddy_addr not in self.free_blocks[current_size]:
                break
            # 移除伙伴块
            self.free_blocks[current_size].remove(current_addr)
            self.free_blocks[current_size].remove(buddy_addr)
            if not self.free_blocks[current_size]:
                del self.free_blocks[current_size]
            # 合并后的块
            current_addr = min(current_addr, buddy_addr)
            current_size *= 2
            if current_size not in self.free_blocks:
                self.free_blocks[current_size] = []
            self.free_blocks[current_size].append(current_addr)
        
        # 内存释放后，尝试处理等待队列
        self._process_waiting_queue()
    
    # 处理等待队列中的请求
    def _process_waiting_queue(self):
        if not self.waiting_queue:
            return
        
        # 复制等待队列，以便在迭代过程中安全地移除元素
        pending_requests = self.waiting_queue.copy()
        self.waiting_queue = []
        
        for process_id, size in pending_requests:
            success = self.allocate(process_id, size)
            if not success:  # 如果分配失败，会自动重新加入等待队列
                pass  # 不需要额外操作，因为allocate会处理

    def get_state(self):
        blocks = []
        # 收集已分配的块
        for pid, (addr, size) in self.allocated_blocks.items():
            blocks.append((addr, pid))
        # 收集空闲的块
        for size in self.free_blocks:
            for addr in self.free_blocks[size]:
                blocks.append((addr, True))
        # 按地址排序
        blocks.sort()
        return blocks
    
    # 获取等待队列信息
    def get_waiting_queue(self):
        return self.waiting_queue.copy()

具体代码注解如注释所示

python的字典这么一个特殊的数据类型还是蛮好用的

test

test.py

from buddy_system import buddy_system

def test1():
    system = buddy_system(2048,1)
    system.allocate(0,1024)
    assert system.get_state() == [(0,0),(1024,True)]
    system.free(0)
    assert system.get_state() == [(0, True)]
    print("test1 passed")

def test2():
    system = buddy_system(1024, 64)
    system.allocate(0, 128)   # 分配128 => 实际分配128（块大小128）
    system.allocate(1, 64)    # 分配64 => 分配块大小64
    system.allocate(2, 256)   # 分配256 => 分配块大小256
    assert system.get_state() == [
        (0, 0), (128, 1), (192, True), (256, 2), (512, True)
    ], "分配后状态错误"
    
    system.free(0)            # 释放128，合并成256
    system.free(1)            # 释放64，合并成128，但无法与相邻块合并
    assert system.get_state() == [
        (0, True), (256, 2), (512, True)
    ], "释放后合并错误"
    print("test2 passed")


def test3():
    system = buddy_system(512, 32)
    system.allocate(0, 32)    # 分配32 => 块大小32
    system.allocate(1, 32)    # 分配32 => 块大小32
    assert system.get_state() == [
        (0, 0), (32, 1), (64, True),(128, True), (256, True)
    ], "最小块分配错误"
    
    system.free(0)
    system.free(1)
    assert system.get_state() == [(0, True)], "最小块释放后合并失败"
    print("test3 passed")

def test4():
    system = buddy_system(512, 64)
    system.allocate(0, 256)
    system.allocate(1, 256)   # 分配第二个256块（总内存512）
    try:
        system.allocate(2, 1) # 尝试分配1字节（实际需要64字节），但无空闲块
        assert False, "未抛出内存不足异常"
    except MemoryError:
        pass
    assert system.get_state() == [(0, 0), (256, 1)], "内存分配异常后状态错误"
    print("test4 passed")

def test5():
    system = buddy_system(2048, 128)
    # 分配并释放形成碎片
    system.allocate(0, 256)   # 分配256 => 实际分配256
    system.allocate(1, 128)   # 分配128 => 实际分配128
    system.allocate(2, 512)   # 分配512 => 实际分配512
    system.free(0)            # 释放256，与空闲伙伴合并为512
    system.free(1)            # 释放128，无法合并
    system.free(2)            # 释放512，合并为1024
    assert system.get_state() == [
        (0, True)
    ], "复杂合并后状态错误"
    print("test5 passed")



test1()
test2()
test3()
test4()
test5()

我在原有的一个test上补充了四个

检查其余情况

kmalloc

Makefile

ifdef KERNELRELEASE
	obj-m := kmalloc.o
else
	KERNELDIR ?= /usr/lib/modules/$(shell uname -r)/build
	PWD := $(shell pwd)
default:
	$(MAKE) -C $(KERNELDIR) M=$(PWD) modules
endif
.PHONY:clean
clean:
	-rm *.mod.c *.o *.order *.symvers *.ko

kmalloc.c

#include <linux/module.h>
#include <linux/slab.h>

MODULE_LICENSE("GPL");

unsigned char *kmallocmem1;
unsigned char *kmallocmem2;

static int __init mem_module_init(void) {
  printk("Start kmalloc!\n");

  // 使用 kmalloc 分配 1KB 的内存
  kmallocmem1 = kmalloc(1024, GFP_KERNEL);
  if (kmallocmem1 != NULL) {
    printk(KERN_ALERT "kmallocmem1 addr = %lx\n", (unsigned long)kmallocmem1);
  } else {
    printk("Failed to allocate kmallocmem1!\n");
  }

  // 使用 kmalloc 分配 8KB 的内存
  kmallocmem2 = kmalloc(8192, GFP_KERNEL);
  if (kmallocmem2 != NULL) {
    printk(KERN_ALERT "kmallocmem2 addr = %lx\n", (unsigned long)kmallocmem2);
  } else {
    printk("Failed to allocate kmallocmem2!\n");
  }

  return 0;
}

static void __exit mem_module_exit(void) {
  // 释放用 kmalloc 分配的内存
  kfree(kmallocmem1);
  kfree(kmallocmem2);

  printk("Exit kmalloc!\n");
}

module_init(mem_module_init);
module_exit(mem_module_exit);

具体如注释所见 GFP_KERNEL表示从内核分配空间

运行结果如上图所示

该部分内存位于内核中

vmalloc

Makefile

ifdef KERNELRELEASE
	obj-m := vmalloc.o
else
	KERNELDIR ?= /usr/lib/modules/$(shell uname -r)/build
	PWD := $(shell pwd)
default:
	$(MAKE) -C $(KERNELDIR) M=$(PWD) modules
endif
.PHONY:clean
clean:
	-rm *.mod.c *.o *.order *.symvers *.ko

vmalloc.c

#include <linux/module.h>
#include <linux/vmalloc.h>

MODULE_LICENSE("GPL");

unsigned char *vmallocmem1;
unsigned char *vmallocmem2;
unsigned char *vmallocmem3;

static int __init mem_module_init(void) {
  printk("Start vmalloc!\n");

  // 使用 vmalloc 分配 8KB 的内存
  vmallocmem1 = vmalloc(8192);
  if (vmallocmem1 != NULL) {
    printk("vmallocmem1 addr = %lx\n", (unsigned long)vmallocmem1);
  } else {
    printk("Failed to allocate vmallocmem1!\n");
  }

  // 使用 vmalloc 分配 1MB 的内存
  vmallocmem2 = vmalloc(1024 * 1024);
  if (vmallocmem2 != NULL) {
    printk("vmallocmem2 addr = %lx\n", (unsigned long)vmallocmem2);
  } else {
    printk("Failed to allocate vmallocmem2!\n");
  }

  // 使用 vmalloc 分配 64MB 的内存
  vmallocmem3 = vmalloc(64 * 1024 * 1024);
  if (vmallocmem3 != NULL) {
    printk("vmallocmem3 addr = %lx\n", (unsigned long)vmallocmem3);
  } else {
    printk("Failed to allocate vmallocmem3!\n");
  }
  return 0;
}

static void __exit mem_module_exit(void) {
  // 释放用 vmalloc 分配的内存
  vfree(vmallocmem1);
  vfree(vmallocmem2);
  vfree(vmallocmem3);
  printk("Exit vmalloc!\n");
}

module_init(mem_module_init);
module_exit(mem_module_exit);

基本就是按照文档来，没什么特别的

结果显示分配的内存是内核中的

问题

内核内存分配的函数可以直接在用户程序中调用吗？ 不可以。用户程序运行在用户态，而kmalloc、vmalloc等函数是内核态的内存分配接口，需要通过内核模块在内核上下文中调用。用户程序无法直接调用这些函数，必须通过系统调用（如malloc）或驱动接口间接申请内核内存。
为什么要区分用户空间内存和内核空间内存？在kmalloc函数中使用GFP_USER的flag会怎样？
- 区分原因：
  1. 安全性：防止用户程序直接访问或修改内核数据，避免系统崩溃或安全漏洞。
  2. 稳定性：内核需要独立的内存管理机制以保证核心功能的可靠运行。
  3. 权限隔离：用户程序无法直接操作硬件资源，需通过内核提供的接口。
- 使用GFP_USER的后果： GFP_USER标志用于从用户空间分配内存，但kmalloc是内核函数，其分配的内存默认要求物理连续且用于内核操作。若错误使用GFP_USER，可能违反内核内存分配规则（如物理连续性），导致分配失败或系统不稳定。
什么是物理内存、虚拟内存？为什么要虚拟内存？
- 物理内存：实际的硬件内存（RAM），由物理地址直接寻址。
- 虚拟内存：操作系统通过页表映射机制为进程提供的逻辑地址空间，独立于物理内存。
- 虚拟内存的作用：
  1. 内存隔离：每个进程拥有独立的虚拟地址空间，避免相互干扰。
  2. 扩展可用内存：通过分页和交换技术，允许进程使用超过物理内存的地址空间。
  3. 简化编程：进程无需关心物理内存布局，只需操作连续的虚拟地址。
  4. 保护机制：通过权限位限制非法访问（如内核空间禁止用户程序直接访问）。
有办法能看到或计算内存分配的虚拟地址对应的物理地址吗？
- 内核空间：可以通过virt_to_phys()函数将内核虚拟地址转换为物理地址（需在内核模块中调用）。
- 用户空间：用户程序的虚拟地址到物理地址的映射由操作系统管理，普通程序无法直接获取。需通过内核模块或调试工具（如/proc/<pid>/pagemap）结合特权操作实现，但通常不推荐且受权限限制。

伙伴系统

buddy_system.py

test

kmalloc

vmalloc

Makefile

vmalloc.c

问题

📖 目录