メモリ管理
仮想メモリの仕組み
参考ドキュメント
Intel® 64 and IA-32 Architectures Software Developer's Manual, Combined Volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4 Volume 3 (3A, 3B, 3C, & 3D): System Programming GuideCHAPTER 5 PAGING 参照
リニアメモリ <-> 物理メモリ変換
4レベルページングによるリニアアドレス変換
エントリの種類ごとの形式
ページング機能の利用手順
初期設定
ページディレクトリテーブルの設定
ページテーブルの設定
CR3にページディレクトリテーブルのアドレスを設定
IDTにページフォルトハンドラを登録
CR0のPGビットを1にセットしてページングをONにする
ページフォルトハンドラ
あまり使われていない論理ページを選択
ページアウト
ページアウトしたページに物理ページとの対応を解除（PTEのPビットを0にリセット）
ページフォルトの発生したページに物理ページを対応させる（PTEのPビットを1にセット）
TLBをフラッシュ
ページイン
主要な変数・構造体
Page Table Entry サイズ
説明 : Page Table 内の1データのサイズを定義
パス : sys/amd64/include/pmap.h
typedef u_int64_t pd_entry_t; // Page Table Entry Size
typedef u_int64_t pt_entry_t; // Page Directory Entry Size
typedef u_int64_t pdp_entry_t; // Page Directory Pointer Table Entry Size
typedef u_int64_t pml4_entry_t; // Page Map Level 4 Entry Size
メモリをページとして扱うときの管理構造
path :
// Page Map Level 4 entry type
static pml4_entry_t *PT4;
// Page Directory Pointer entry type
static pdp_entry_t *PT3;
static pdp_entry_t *PT3_l, *PT3_u;
// Page Directory entry type
static pd_entry_t *PT2;
static pd_entry_t *PT2_l0, *PT2_l1, *PT2_l2, *PT2_l3, *PT2_u0, *PT2_u1;
プロセス単位の仮想メモリアドレス
erDiagram
vmspace ||--|| vm_map : "vm_map"
vmspace ||--|| pmap : "vm_pmap"
vmspace ||..|| shmmap_state : "vm_shm"
vm_map ||--|| sx : "lock"
vm_map ||--|| vm_map_entry : "header"
vm_map ||..|| vm_map_entry : "root"
vm_map ||..|| pmap : "pmap"
vm_map ||..|| mtx : "system_mtx"
vm_map_entry ||..|| vm_map_entry : "*prev, *next, *left, *right"
vm_map_entry ||--|| vm_map_object : "object"
vm_map_object ||..|| vm_object : "vm_object"
vm_map_object ||..|| vm_map : "sub_map"
vm_object ||..|| vm_object : "backing_object"
vmspace {
vm_map vm_map
shmmap_state *vm_shm
pmap vm_pmap
}
vm_map {
vm_map_entry header
vm_map_entry root
sx lock
mtx system_mtx
int nentries
vm_size_t size
pmap_t pmap
}
pmap {
pml4_entry_t pm_pml4
pml4_entry_t pm_pml4u
uint64_t pm_cr3
uint64_t pm_ucr3
pmap_type pm_type
}
shmmap_state {
vm_offset_t va
int shmid
}
vm_map_entry {
vm_map_entry *prev
vm_map_entry *next
vm_map_entry *left
vm_map_entry *right
vm_map_object object
ucred *cred
thread *wiring_thread
}
vm_map_object {
vm_object vm_object
vm_map sub_map
}
vm_object {
vm_object backing_object
vm_ooffset_t backing_object_offset
}
sx {
lock_object lock_object
uintptr_t sx_lock
}
mtx {
lock_object lock_object
uintptr_t mtx_lock
}
実線 : 構造体の実体をそのまま内側に持っている
点線 : ポインタで指しているだけで、実体は別の場所にある
vmspace（sys/vm/vm_map.h）
プロセスのアドレス空間を表現するための、機種依存・機種非依存の両方の情報を包含する構造体
/*
* Shareable process virtual address space.
*
* List of locks
* (c) const until freed
*/
struct vmspace {
struct vm_map vm_map; /* VM address map */
struct shmmap_state *vm_shm; /* SYS5 shared memory private data XXX */
segsz_t vm_swrss; /* resident set size before last swap */
segsz_t vm_tsize; /* text size (pages) XXX */
segsz_t vm_dsize; /* data size (pages) XXX */
segsz_t vm_ssize; /* stack size (pages) */
caddr_t vm_taddr; /* (c) user virtual address of text */
caddr_t vm_daddr; /* (c) user virtual address of data */
caddr_t vm_maxsaddr; /* user VA at max stack growth */
volatile int vm_refcnt; /* number of references */
/*
* Keep the PMAP last, so that CPU-specific variations of that
* structure on a single architecture don't result in offset
* variations of the machine-independent fields in the vmspace.
*/
struct pmap vm_pmap; /* private physical map */
};
vm_map（sys/vm/vm_map.h）
機種非依存な仮想アドレス空間を表現するための最上位のデータ構造
/*
* A map is a set of map entries. These map entries are
* organized both as a binary search tree and as a doubly-linked
* list. Both structures are ordered based upon the start and
* end addresses contained within each map entry.
*
* Counterintuitively, the map's min offset value is stored in
* map->header.end, and its max offset value is stored in
* map->header.start.
*
* The list header has max start value and min end value to act
* as sentinels for sequential search of the doubly-linked list.
* Sleator and Tarjan's top-down splay algorithm is employed to
* control height imbalance in the binary search tree.
*
* List of locks
* (c) const until freed
*/
struct vm_map {
struct vm_map_entry header; /* List of entries */
/*
map min_offset header.end (c)
map max_offset header.start (c)
*/
struct sx lock; /* Lock for map data */
struct mtx system_mtx;
int nentries; /* Number of entries */
vm_size_t size; /* virtual size */
u_int timestamp; /* Version number */
u_char needs_wakeup;
u_char system_map; /* (c) Am I a system map? */
vm_flags_t flags; /* flags for this vm_map */
vm_map_entry_t root; /* Root of a binary search tree */
pmap_t pmap; /* (c) Physical map */
int busy;
};
vm_map_entry（sys/vm/vm_map.h）
保護状態や継承される属性、および同じ外部記憶オブジェクトを共有する、仮想的に連続したアドレス範囲からバッキングストアの vm_object へのマッピングを記述する構造体
/*
* Address map entries consist of start and end addresses,
* a VM object (or sharing map) and offset into that object,
* and user-exported inheritance and protection information.
* Also included is control information for virtual copy operations.
*/
struct vm_map_entry {
struct vm_map_entry *prev; /* previous entry */
struct vm_map_entry *next; /* next entry */
struct vm_map_entry *left; /* left child in binary search tree */
struct vm_map_entry *right; /* right child in binary search tree */
vm_offset_t start; /* start address */
vm_offset_t end; /* end address */
vm_offset_t pad0;
vm_offset_t next_read; /* vaddr of the next sequential read */
vm_size_t adj_free; /* amount of adjacent free space */
vm_size_t max_free; /* max free space in subtree */
union vm_map_object object; /* object I point to */
vm_ooffset_t offset; /* offset into object */
vm_eflags_t eflags; /* map entry flags */
vm_prot_t protection; /* protection code */
vm_prot_t max_protection; /* maximum protection */
vm_inherit_t inheritance; /* inheritance */
uint8_t read_ahead; /* pages in the read-ahead window */
int wired_count; /* can be paged if = 0 */
struct ucred *cred; /* tmp storage for creator ref */
struct thread *wiring_thread;
};
vm_map_object（sys/vm/vm_map.h）
/*
* Objects which live in maps may be either VM objects, or
* another map (called a "sharing map") which denotes read-write
* sharing with other maps.
*/
union vm_map_object {
struct vm_object *vm_object; /* object object */
struct vm_map *sub_map; /* belongs to another map */
};
vm_object（sys/vm/vm_object.h）
物理メモリや命令やデータを含む各種資源のデータの出自を記述する構造体
struct vm_object {
struct rwlock lock;
TAILQ_ENTRY(vm_object) object_list; /* list of all objects */
LIST_HEAD(, vm_object) shadow_head; /* objects that this is a shadow for */
LIST_ENTRY(vm_object) shadow_list; /* chain of shadow objects */
struct pglist memq; /* list of resident pages */
struct vm_radix rtree; /* root of the resident page radix trie*/
vm_pindex_t size; /* Object size */
int generation; /* generation ID */
int ref_count; /* How many refs?? */
int shadow_count; /* how many objects that this is a shadow for */
vm_memattr_t memattr; /* default memory attribute for pages */
objtype_t type; /* type of pager */
u_short flags; /* see below */
u_short pg_color; /* (c) color of first page in obj */
u_int paging_in_progress; /* Paging (in or out) so don't collapse or destroy */
int resident_page_count; /* number of resident pages */
struct vm_object *backing_object; /* object that I'm a shadow of */
vm_ooffset_t backing_object_offset;/* Offset in backing object */
TAILQ_ENTRY(vm_object) pager_object_list; /* list of all objects of this pager type */
LIST_HEAD(, vm_reserv) rvq; /* list of reservations */
void *handle;
union {
/*
* VNode pager
*
* vnp_size - current size of file
*/
struct {
off_t vnp_size;
vm_ooffset_t writemappings;
} vnp;
/*
* Device pager
*
* devp_pglist - list of allocated pages
*/
struct {
TAILQ_HEAD(, vm_page) devp_pglist;
struct cdev_pager_ops *ops;
struct cdev *dev;
} devp;
/*
* SG pager
*
* sgp_pglist - list of allocated pages
*/
struct {
TAILQ_HEAD(, vm_page) sgp_pglist;
} sgp;
/*
* Swap pager
*
* swp_tmpfs - back-pointer to the tmpfs vnode,
* if any, which uses the vm object
* as backing store. The handle
* cannot be reused for linking,
* because the vnode can be
* reclaimed and recreated, making
* the handle changed and hash-chain
* invalid.
*
* swp_blks - pc-trie of the allocated swap blocks.
*
*/
struct {
void *swp_tmpfs;
struct pctrie swp_blks;
} swp;
} un_pager;
struct ucred *cred;
vm_ooffset_t charge;
void *umtx_data;
};
sx（sys/sys/_sx.h）
/*
* Shared/exclusive lock main structure definition.
*/
struct sx {
struct lock_object lock_object;
volatile uintptr_t sx_lock;
};
mtx（sys/sys/_mutex.h）
/*
* Sleep/spin mutex.
*
* All mutex implementations must always have a member called mtx_lock.
* Other locking primitive structures are not allowed to use this name
* for their members.
* If this rule needs to change, the bits in the mutex implementation must
* be modified appropriately.
*/
struct mtx {
struct lock_object lock_object; /* Common lock properties. */
volatile uintptr_t mtx_lock; /* Owner and flags. */
};
shmmap_state（sys/kern/sysv_shm.c）
struct shmmap_state {
vm_offset_t va;
int shmid;
};
pmap（sys/amd64/include/pmap.h）
/*
* The kernel virtual address (KVA) of the level 4 page table page is always
* within the direct map (DMAP) region.
*/
struct pmap {
struct mtx pm_mtx;
pml4_entry_t *pm_pml4; /* KVA of level 4 page table */
pml4_entry_t *pm_pml4u; /* KVA of user l4 page table */
uint64_t pm_cr3;
uint64_t pm_ucr3;
TAILQ_HEAD(,pv_chunk) pm_pvchunk; /* list of mappings in pmap */
cpuset_t pm_active; /* active on cpus */
enum pmap_type pm_type; /* regular or nested tables */
struct pmap_statistics pm_stats; /* pmap statistics */
struct vm_radix pm_root; /* spare page table pages */
long pm_eptgen; /* EPT pmap generation id */
int pm_flags;
struct pmap_pcids pm_pcids[MAXCPU];
};
主要なマクロ
#define G(x) (1ULL * (x) * 1024 * 1024 * 1024)
1ULL : 1 unsigned long long を意味する