メモリ管理 =========================== 仮想メモリの仕組み --------------------------- **参考ドキュメント** - 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 参照 リニアメモリ <-> 物理メモリ変換 ^^^^^ .. image:: ../_static/images/メモリ変換概念図.png :target: ../_static/images/メモリ変換概念図.png 4レベルページングによるリニアアドレス変換 ^^^^^ .. image:: ../_static/images/4-Level-Paging-リニアアドレス変換.png :target: ../_static/images/4-Level-Paging-リニアアドレス変換.png エントリの種類ごとの形式 ^^^^^ .. image:: ../_static/images/エントリの種類ごとの形式-4レベルページング.png :target: ../_static/images/エントリの種類ごとの形式-4レベルページング.png ページング機能の利用手順 ^^^^^ - 初期設定 - ページディレクトリテーブルの設定 - ページテーブルの設定 - CR3にページディレクトリテーブルのアドレスを設定 - IDTにページフォルトハンドラを登録 - CR0のPGビットを1にセットしてページングをONにする - ページフォルトハンドラ - あまり使われていない論理ページを選択 - ページアウト - ページアウトしたページに物理ページとの対応を解除（PTEのPビットを0にリセット） - ページフォルトの発生したページに物理ページを対応させる（PTEのPビットを1にセット） - TLBをフラッシュ - ページイン 主要な変数・構造体 --------------------------- Page Table Entry サイズ ^^^^^ - 説明 : Page Table 内の1データのサイズを定義 - パス : sys/amd64/include/pmap.h .. code-block:: c 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 : .. code-block:: c // 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; プロセス単位の仮想メモリアドレス ^^^^^ .. mermaid:: 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） ~~~~~ - プロセスのアドレス空間を表現するための、機種依存・機種非依存の両方の情報を包含する構造体 .. code-block:: c /* * 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） ~~~~~ - 機種非依存な仮想アドレス空間を表現するための最上位のデータ構造 .. code-block:: c /* * 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** へのマッピングを記述する構造体 .. code-block:: c /* * 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） ~~~~~ .. code-block:: c /* * 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） ~~~~~ - 物理メモリや命令やデータを含む各種資源のデータの出自を記述する構造体 .. code-block:: c 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） ~~~~~ .. code-block:: c /* * Shared/exclusive lock main structure definition. */ struct sx { struct lock_object lock_object; volatile uintptr_t sx_lock; }; mtx（sys/sys/_mutex.h） ~~~~~ .. code-block:: c /* * 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） ~~~~~ .. code-block:: c struct shmmap_state { vm_offset_t va; int shmid; }; pmap（sys/amd64/include/pmap.h） ~~~~~ .. code-block:: c /* * 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]; }; 主要なマクロ --------------------------- .. code-block:: c #define G(x) (1ULL * (x) * 1024 * 1024 * 1024) - 1ULL : 1 unsigned long long を意味する - 主要な関数 --------------------------- .. toctree:: :maxdepth: 1 setup_runqs