Skip to content

Commit fec09ad

Browse files
yangminzyangminz
committed
add swap
1 parent f18e73a commit fec09ad

File tree

3 files changed

+151
-2
lines changed

3 files changed

+151
-2
lines changed

‎src/hardware/cpu/mmu.c‎

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,9 @@
2020
static uint64_t page_walk(uint64_t vaddr_value);
2121
static void page_fault_handler(pte4_t *pte, address_t vaddr);
2222

23+
int swap_in(uint64_t daddr, uint64_t ppn);
24+
int swap_out(uint64_t daddr, uint64_t ppn);
25+
2326
// consider this function va2pa as functional
2427
uint64_t va2pa(uint64_t vaddr)
2528
{
@@ -151,9 +154,12 @@ static uint64_t page_walk(uint64_t vaddr_value)
151154
static void page_fault_handler(pte4_t *pte, address_t vaddr)
152155
{
153156
// select one victim physical page to swap to disk
157+
assert(pte->present == 0);
154158

155159
// this is the selected ppn for vaddr
156160
int ppn = -1;
161+
pte4_t *victim = NULL;
162+
uint64_t daddr = 0xffffffffffffffff;
157163

158164
// 1. try to request one free physical page from DRAM
159165
// kernel's responsibility
@@ -181,7 +187,86 @@ static void page_fault_handler(pte4_t *pte, address_t vaddr)
181187

182188
// 2. no free physical page: select one clean page (LRU) and overwrite
183189
// in this case, there is no DRAM - DISK transaction
190+
int lru_ppn = -1;
191+
int lru_time = -1;
192+
for (int i = 0; i < MAX_NUM_PHYSICAL_PAGE; ++ i)
193+
{
194+
if (page_map[i].dirty == 0 &&
195+
lru_time < page_map[i].time)
196+
{
197+
lru_time = page_map[i].time;
198+
lru_ppn = i;
199+
}
200+
}
201+
202+
if (-1 != lru_ppn && lru_ppn < MAX_NUM_PHYSICAL_PAGE)
203+
{
204+
ppn = lru_ppn;
205+
206+
// reversed mapping
207+
victim = page_map[ppn].pte4;
208+
209+
victim->pte_value = 0;
210+
victim->present = 0;
211+
victim->daddr = page_map[ppn].daddr;
212+
213+
// load page from disk to physical memory first
214+
daddr = pte->daddr;
215+
swap_in(pte->daddr, ppn);
216+
217+
pte->pte_value = 0;
218+
pte->present = 1;
219+
pte->ppn = ppn;
220+
pte->dirty = 0;
221+
222+
page_map[ppn].allocated = 1;
223+
page_map[ppn].time = 0;
224+
page_map[ppn].dirty = 0;
225+
page_map[ppn].pte4 = pte;
226+
page_map[ppn].daddr = daddr;
227+
228+
return;
229+
}
184230

185231
// 3. no free nor clean physical page: select one LRU victim
186232
// write back (swap out) the DIRTY victim to disk
233+
lru_ppn = -1;
234+
lru_time = -1;
235+
for (int i = 0; i < MAX_NUM_PHYSICAL_PAGE; ++ i)
236+
{
237+
if (lru_time < page_map[i].time)
238+
{
239+
lru_time = page_map[i].time;
240+
lru_ppn = i;
241+
}
242+
}
243+
244+
assert(0 <= lru_ppn && lru_ppn < MAX_NUM_PHYSICAL_PAGE);
245+
246+
ppn = lru_ppn;
247+
248+
// reversed mapping
249+
victim = page_map[ppn].pte4;
250+
251+
// write back
252+
swap_out(page_map[ppn].daddr, ppn);
253+
254+
victim->pte_value = 0;
255+
victim->present = 0;
256+
victim->daddr = page_map[ppn].daddr;
257+
258+
// load page from disk to physical memory first
259+
daddr = pte->daddr;
260+
swap_in(daddr, ppn);
261+
262+
pte->pte_value = 0;
263+
pte->present = 1;
264+
pte->ppn = ppn;
265+
pte->dirty = 0;
266+
267+
page_map[ppn].allocated = 1;
268+
page_map[ppn].time = 0;
269+
page_map[ppn].dirty = 0;
270+
page_map[ppn].pte4 = pte;
271+
page_map[ppn].daddr = daddr;
187272
}

‎src/hardware/memory/swap.c‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
/* BCST - Introduction to Computer Systems
2+
* Author: [email protected]
3+
* Github: https://github.com/yangminz/bcst_csapp
4+
* Bilibili: https://space.bilibili.com/4564101
5+
* Zhihu: https://www.zhihu.com/people/zhao-yang-min
6+
* This project (code repository and videos) is exclusively owned by yangminz
7+
* and shall not be used for commercial and profitting purpose
8+
* without yangminz's permission.
9+
*/
10+
11+
// Dynamic Random Access Memory
12+
#include <string.h>
13+
#include <assert.h>
14+
#include <stdio.h>
15+
#include <stdlib.h>
16+
#include "headers/cpu.h"
17+
#include "headers/memory.h"
18+
#include "headers/common.h"
19+
#include "headers/address.h"
20+
21+
// each swap file is swap page
22+
// each line of this swap page is one uint64
23+
#define SWAP_PAGE_FILE_LINES 512
24+
25+
// disk address counter
26+
static uint64_t internal_swap_daddr = 0;
27+
28+
int swap_in(uint64_t daddr, uint64_t ppn)
29+
{
30+
FILE *fr = NULL;
31+
char filename[128];
32+
sprintf(filename, "../files/swap/page-%ld.txt", daddr);
33+
fr = fopen(filename, "r");
34+
assert(fr != NULL);
35+
36+
uint64_t ppn_ppo = ppn << PHYSICAL_PAGE_OFFSET_LENGTH;
37+
char buf[64] = {'0'};
38+
for (int i = 0; i < SWAP_PAGE_FILE_LINES; ++ i)
39+
{
40+
char *str = fgets(buf, 64, fr);
41+
*((uint64_t *)(&pm[ppn_ppo + i * 8])) = string2uint(str);
42+
}
43+
fclose(fr);
44+
}
45+
46+
int swap_out(uint64_t daddr, uint64_t ppn)
47+
{
48+
FILE *fw = NULL;
49+
char filename[128];
50+
sprintf(filename, "../files/swap/page-%ld.txt", daddr);
51+
fw = fopen(filename, "w");
52+
assert(fw != NULL);
53+
54+
uint64_t ppn_ppo = ppn << PHYSICAL_PAGE_OFFSET_LENGTH;
55+
for (int i = 0; i < SWAP_PAGE_FILE_LINES; ++ i)
56+
{
57+
fprintf(fw, "0x%16lx\n", *((uint64_t *)(&pm[ppn_ppo + i * 8])));
58+
}
59+
fclose(fw);
60+
}

‎src/headers/memory.h‎

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -67,7 +67,7 @@ typedef union
6767
struct
6868
{
6969
uint64_t _present : 1;
70-
uint64_t swap_id : 63; // disk address
70+
uint64_t daddr : 63; // disk address
7171
};
7272
} pte123_t; // PGD, PUD, PMD
7373

@@ -96,7 +96,7 @@ typedef union
9696
struct
9797
{
9898
uint64_t _present : 1; // present = 0
99-
uint64_t swap_id : 63; // disk address
99+
uint64_t daddr : 63; // disk address
100100
};
101101
} pte4_t; // PT
102102

@@ -107,7 +107,11 @@ typedef struct
107107
int dirty;
108108
int time; // LRU cache
109109

110+
// real world: mapping to anon_vma or address_space
111+
// we simply the situation here
112+
// TODO: if multiple processes are using this page? E.g. Shared library
110113
pte4_t *pte4; // the reversed mapping: from PPN to page table entry
114+
uint64_t daddr; // binding the revesed mapping with mapping to disk
111115
} pd_t;
112116

113117
// for each pagable (swappable) physical page

0 commit comments

Comments
 (0)