OS pintos内存管理

OS

https://www.zybuluo.com/SovietPower/note/1885155

palloc.c

页分配器，用于分配页大小的内存。
系统内存被分为两部分：用于用户（虚拟）内存页的用户池（user pool），用于其它东西的内核池（kernel pool）。因为无论用户进程在做什么，内核都需要有它自己能用的内存。
默认情况下，RAM的一半用于用户池、一半用于内核池。实际情况下内核池应该要更大，但pintos只用来展示，所以无所谓了。

PGSHIFT, PGBITS, PGSIZE, PGMASK

分别表示：页中的第一个有效位位置（偏移量）$0$，页大小的位数$12$，页大小$2^{12}$，页有效位的位置的掩码表示$2^{12}-1$。

/* Page offset (bits 0:12). */
#define PGSHIFT 0                          /* Index of first offset bit. */
#define PGBITS  12                         /* Number of offset bits. */
#define PGSIZE  (1 << PGBITS)              /* Bytes in a page. */
#define PGMASK  BITMASK(PGSHIFT, PGBITS)   /* Page offset bits (0:12). */
#define BITMASK(SHIFT, CNT) (((1ul << (CNT)) - 1) << (SHIFT))

pool

内存池。
包含一个互斥锁，一个记录空闲页的位图，该池内存地址的起点。

/* A memory pool. */
struct pool
{
    struct lock lock;                   /* Mutual exclusion. */
    struct bitmap *used_map;            /* Bitmap of free pages. */
    uint8_t *base;                      /* Base of pool. */
};

kernel_pool, user_pool

内核池和用户池，分别用于内核、用户页。

/* Two pools: one for kernel data, one for user pages. */
static struct pool kernel_pool, user_pool;

palloc_init()

初始化页分配器。
用户池最多只能有user_page_limit个页（如果不限制，则默认为总可用页数/2）。
会用设定的页数，初始化用户池；然后用剩余的页数，初始化内核池。

RAM的1MB位置到最后，都是可分配内存。

void palloc_init (size_t user_page_limit);

palloc_get_multiple()

分配连续的page_cnt个页。
具体根据flags中包含的标志位：
若设置了PAL_USER，则从用户池中取出页，否则从内核池中取出页。
若设置了PAL_ZERO，则分配的新页用0填充。
若设置了PAL_ASSERT，则在不能够分配page_cnt个页时，触发内核panic；不设置则只返回NULL。

通过对应池的位图查找连续的page_cnt个空闲页。
若查找成功，返回分配页的起始位置（设空闲页的第一页为page_idx页，则返回池的内存起始位置base加页大小乘page_idx，即pool->base + PGSIZE*page_idx）。

void *palloc_get_multiple (enum palloc_flags flags, size_t page_cnt);

palloc_get_page()

分配一页。即调用palloc_get_multiple (flags, 1)。

void *palloc_get_page (enum palloc_flags flags);

palloc_free_multiple()

释放连续的page_cnt个页。
会将这些区域全部用0xcc填充（便于调试），并更新该池的位图。

void palloc_free_multiple (void *pages, size_t page_cnt);

palloc_free_page()

释放一页。即调用palloc_free_multiple (page, 1)。

void palloc_free_page (void *page);

init_pool()

初始化一个内存池，包含page_cnt。
会先计算page_cnt个页所需的位图大小，然后分配bm_pages页给位图，剩下page_cnt-bm_pages个页为实际存储页。
然后初始化池的位图，并将其起始地址base，设为其位图的结束地址base + bm_pages*PGSIZE。

static void init_pool (struct pool *p, void *base, size_t page_cnt, const char *name);

page_from_pool()

判断一个页是否是从某个内存池中分配的。是则返回true。
通过计算该页的编号是否在该内存池的编号范围内判断。

static bool page_from_pool (const struct pool *pool, void *page);

malloc.c

malloc()的简单实现。
每次请求内存，请求的大小（以字节为单位）会被调整为最近的大于它的$2^k$，并被赋值为一个管理分配的内存块的描述符（该描述符的所有块大小均为$2^k$）。
描述符（descriptor）保存一个空闲块的链表。如果该链表非空，则为请求分配一个链表中的块。否则，调用页分配器创建一页的内存（称为一个arena）（若无可用，则返回NULL），将新的arena分为若干同样大小的块放入空闲链表，再返回其中的一个块。
当释放一个块时，将其添加到它的描述符的空闲块链表中。如果此时该块所在的arena的所有块都已被释放，则将该arena的所有块从空闲块链表中删除，将该arena释放（通过页分配器）。

这种方法不能分配大小超过2KB的块，因为这比一页还大。若要分配较大内存，可调用页分配器分配连续的若干页，并将分配大小存在分配块的arena头部。

desc

描述符。
每个描述符，有其自己的块大小，每个arena（每个页）能包含的块数，空闲块的链表，锁。

struct desc
{
    size_t block_size;          /* Size of each element in bytes. */
    size_t blocks_per_arena;    /* Number of blocks in an arena. */
    struct list free_list;      /* List of free blocks. */
    struct lock lock;           /* Lock. */
};

ARENA_MAGIC

检测arena中是否存在运行错误。

#define ARENA_MAGIC 0x9a548eed

arena

arena，为一页，被分为若干块，保存在描述符中。
保存它所在的描述符（如果分配的连续页，则为NULL）、剩余空闲块数（如果分配的连续页，则为空闲页数）。

/* Arena. */
struct arena
{
    unsigned magic;             /* Always set to ARENA_MAGIC. */
    struct desc *desc;          /* Owning descriptor, null for big block. */
    size_t free_cnt;            /* Free blocks; pages in big block. */
};

block

空闲块。含一个它的链表元素。

/* Free block. */
struct block
{
    struct list_elem free_elem; /* Free list element. */
};

descs, desc_cnt

系统可用的描述符集合及其数量。

/* Our set of descriptors. */
static struct desc descs[10];   /* Descriptors. */
static size_t desc_cnt;         /* Number of descriptors. */

malloc_init()

初始化可用描述符集合。
不同的描述符，保存的块大小不同，分别为$16, 32, 64, ..., 2^{10}, 2^{11}$（小于$2^{PGBITS}$），用于分配不同大小的块。同样，每个arena在该描述符中能保存的块的数量blocks_per_arena也不同。

/* Initializes the malloc() descriptors. */
void malloc_init (void);

malloc()

获取一个大小至少为size字节的空闲块（或连续页）。若没有，返回NULL。
若size不超过$2^{11}$，则找到块大小不小于size的第一个描述符$d$。若$d$的空闲块链表非空，则取出链表的第一个元素，即一个空闲块。否则，调用页分配器获取一个新页，即一个新的arena，将其分为若干对应大小的块，依次放入空闲块链表。
若size超过$2^{11}$，则超过最大块的大小，需调用页分配器为该请求分配page_cnt个新页，即一个新的arena（不属于任何描述符）。

void *malloc (size_t size);

calloc()

分配一个大小为$a\times b$字节的空闲块（或连续页）。分配的区域会被初始化为0。
即调用p = malloc(a*b)，并memset(p, 0, size)。

void *calloc (size_t a, size_t b);

block_size()

返回块block的大小（字节数）。
若该块拥有描述符，则大小为描述符的块大小；否则为arena的页个数乘PGSIZE，再减该块在第一个页的起始位置。

static size_t block_size (void *block);

realloc()

将块的大小改为new_size。
通过新建一个大小为new_size的块，然后将old_block的所有内容复制到新块中实现（若新块大小不够，则只复制部分）。原来的块会被释放。

若new_size等于0，则等同于free(old_block)；若old_block为NULL，则等同于malloc(new_size)。

void *realloc (void *old_block, size_t new_size);

free()

释放块p。
若p是一个块，设d为其描述符，a为其所属的arena，则将其放到d的空闲块链表中。若此时a拥有的块全部被释放（++a->free_cnt >= d->blocks_per_arena），则将a的全部块从d的空闲链表中删除，释放a。
若p是连续的页，则调用页分配器释放该连续页，即palloc_free_multiple (a, a->free_cnt)。

void free (void *p);

block_to_arena()

返回块b所属的arena。
因为arena为一整页，所以b所在的页的起始地址（pg_round_down(b)），就是其arena的地址。

static struct arena *block_to_arena (struct block *b);

arena_to_block()

返回一个arena a拥有的第idx个块。
第idx个块的起始地址，即为：a的起始地址，加上*a的大小（arena结构占用的空间），再加idx乘a的块大小，即(struct block *) ((uint8_t *) a + sizeof *a + idx * a->desc->block_size)。

static struct block *arena_to_block (struct arena *a, size_t idx);