您是第 位访客

disksim-3.0 with flashsim 源码分析(六):垃圾回收

仍然以DFTL为例,在 dftl.c 文件中有一个 opm_write() 函数,前面对这个函数也进行过介绍,这个函数主要是实现 dftl 的写操作逻辑。在这个函数中会进行 GC 操作的判断,先调用 nand_get_free_blk(0) 函数,如果返回 -1 ,则表示需要进行垃圾回收,当整个 SSD 的空闲页大于阈值的时候就停止垃圾回收。这部分的代码,如下所示:

1
2
3
4
5
6
7
8
9
10
11
if (free_page_no[small] >= SECT_NUM_PER_BLK){ //当前正在写的 block 已经写完了
if ((free_blk_no[small] = nand_get_free_blk(0)) == -1){ //申请一个新的block,同时判断是否需要进行GC
while (free_blk_num < min_fb_num ){
opm_gc_run(small, mapdir_flag); // GC
}
opm_gc_get_free_blk(small, mapdir_flag); // 申请一个新的block
}
else {
free_page_no[small] = 0; //从新的一个blkno开始写
}
}

在 dflt.c 中,进行GC的操作是在 opm_gc_run() 函数中进行的。GC 操作大致分为以下几个步骤:

  1. 选择无效数据最少的 block 进行回收。
  2. 迁移 block 中的有效数据,并同时更新映射表。
  3. 对于被迁移的数据的映射记录没有在缓冲区命中时,需要进行映射表的读写,也就是说需要额外增加两次IO。

注意:在垃圾回收时,如果迁移数据对应的映射记录没有在缓冲区命中,会从闪存中把映射表读入到缓存,更改后又写会闪存,不会放入缓冲区内。

下面具体介绍 opm_gc_run() 函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
int opm_gc_run(int small, int mapdir_flag){
blk_t victim_blk_no; // 需要回收的 blkno
int merge_count;
int i,z, j,m,q, benefit = 0;
int k,old_flag,temp_arr[PAGE_NUM_PER_BLK],temp_arr1[PAGE_NUM_PER_BLK],map_arr[PAGE_NUM_PER_BLK];
int valid_flag,pos;
_u32 copy_lsn[SECT_NUM_PER_PAGE], copy[SECT_NUM_PER_PAGE];
_u16 valid_sect_num, l, s;
victim_blk_no = opm_gc_cost_benefit(); //返回无效sector最多的block作为目标block回收
memset(copy_lsn, 0xFF, sizeof (copy_lsn));
// 只保留free_page_no[small]的后三位(page size:4kb).s则表示当前free sector是在page中的第几个sector
s = k = OFF_F_SECT(free_page_no[small]);
if(!((s == 0) && (k == 0))){
printf("s && k should be 0\n");
exit(0);
}
small = -1;
for( q = 0; q < PAGE_NUM_PER_BLK; q++){
if(nand_blk[victim_blk_no].page_status[q] == 1){ //如果要回收的块是映射块
for( i = 0; i < PAGE_NUM_PER_BLK; i++) {
if(nand_blk[victim_blk_no].page_status[i] == 0 ){
printf("something corrupted1=%d",victim_blk_no);
}
}
small = 0; //map block
break;
}
else if(nand_blk[victim_blk_no].page_status[q] == 0){ //如果要回收的块是数据块
for( i = 0; i < PAGE_NUM_PER_BLK; i++) {
if(nand_blk[victim_blk_no].page_status[i] == 1 ){
printf("something corrupted2",victim_blk_no);
}
}
small = 1; //data block
break;
}
}
ASSERT ( small == 0 || small == 1);
pos = 0;
merge_count = 0; //迁移页的数量
//对block中的每个页进行判断是否需要迁移,如果需要则进行迁移
for (i = 0; i < PAGE_NUM_PER_BLK; i++) {
//如果这个页的状态是 valid 返回 1; invalid 返回 -1;free 返回 0;
valid_flag = nand_oob_read( SECTOR(victim_blk_no, i * SECT_NUM_PER_PAGE));
if(valid_flag == 1){ // 这个页是的状态是 valid
//copy[]记录的是该页中需要转移的 logical sector number,理论上是这个页中的所有sector
valid_sect_num = nand_page_read( SECTOR(victim_blk_no, i * SECT_NUM_PER_PAGE), copy, 1);
merge_count++;
ASSERT(valid_sect_num == SECT_NUM_PER_PAGE);
k=0;
for (j = 0; j < valid_sect_num; j++) {
copy_lsn[k] = copy[j]; // 将copy[]的数据保存到copy_lsn[]
k++;
}
benefit += opm_gc_get_free_blk(small, mapdir_flag); // 申请新的位置来接受迁移的数据
if(nand_blk[victim_blk_no].page_status[i] == 1){ // 迁移的数据是映射表
//更改映射表
mapdir[(copy_lsn[s]/SECT_NUM_PER_PAGE)].ppn = BLK_PAGE_NO_SECT(SECTOR(free_blk_no[small], free_page_no[small]));
opagemap[copy_lsn[s]/SECT_NUM_PER_PAGE].ppn = BLK_PAGE_NO_SECT(SECTOR(free_blk_no[small], free_page_no[small]));
// 写入数据
nand_page_write(SECTOR(free_blk_no[small],free_page_no[small]) & (~OFF_MASK_SECT), copy_lsn, 1, 2);
free_page_no[small] += SECT_NUM_PER_PAGE;
}
else{ //迁移的数据用户数据
//更改映射表
opagemap[BLK_PAGE_NO_SECT(copy_lsn[s])].ppn = BLK_PAGE_NO_SECT(SECTOR(free_blk_no[small], free_page_no[small]));
//写入数据
nand_page_write(SECTOR(free_blk_no[small],free_page_no[small]) & (~OFF_MASK_SECT), copy_lsn, 1, 1);
free_page_no[small] += SECT_NUM_PER_PAGE;
//如果修改的页的映射存在缓存中
if((opagemap[BLK_PAGE_NO_SECT(copy_lsn[s])].map_status == MAP_REAL) || (opagemap[BLK_PAGE_NO_SECT(copy_lsn[s])].map_status == MAP_GHOST)){
delay_flash_update++;
opagemap[BLK_PAGE_NO_SECT(copy_lsn[s])].update = 1; //added by H.Chen
}
//如果该映射不在缓存中
else {
map_arr[pos] = copy_lsn[s]; //记录哪些被迁移的sector的映射记录没有命中
pos++;
}
}
}
}
// temp_arr[] 记录sector的映射记录所在的逻辑映射页对应的物理地址
// temp_arr1[] 与temp_arr[]对应的sector的地址
// temp_arr1[i] 的映射记录所在的逻辑映射页对应的物理映射页地址是 temp_arr[i]
for(i=0;i < PAGE_NUM_PER_BLK;i++) {
temp_arr[i]=-1;
}
k=0;
for(i =0 ; i < pos; i++) {
old_flag = 0;
for( j = 0 ; j < k; j++) {
if(temp_arr[j] == mapdir[((map_arr[i]/SECT_NUM_PER_PAGE)/MAP_ENTRIES_PER_PAGE)].ppn) {
if(temp_arr[j] == -1){
printf("something wrong");
ASSERT(0);
}
old_flag = 1;
break;
}
}
if( old_flag == 0 ) {
temp_arr[k] = mapdir[((map_arr[i]/SECT_NUM_PER_PAGE)/MAP_ENTRIES_PER_PAGE)].ppn;
temp_arr1[k] = map_arr[i];
k++;
}
else
save_count++;
}
for ( i=0; i < k; i++) {
if (free_page_no[0] >= SECT_NUM_PER_BLK) {
if((free_blk_no[0] = nand_get_free_blk(1)) == -1){
printf("we are in big trouble shudnt happen");
}
free_page_no[0] = 0;
}
//读入映射表
nand_page_read(temp_arr[i]*SECT_NUM_PER_PAGE,copy,1);
//将原来的标记为无效
for(m = 0; m<SECT_NUM_PER_PAGE; m++){
nand_invalidate(mapdir[((temp_arr1[i]/SECT_NUM_PER_PAGE)/MAP_ENTRIES_PER_PAGE)].ppn*SECT_NUM_PER_PAGE+m, copy[m]);
}
nand_stat(OOB_WRITE);
//更新映射表
mapdir[((temp_arr1[i]/SECT_NUM_PER_PAGE)/MAP_ENTRIES_PER_PAGE)].ppn = BLK_PAGE_NO_SECT(SECTOR(free_blk_no[0], free_page_no[0]));
opagemap[((temp_arr1[i]/SECT_NUM_PER_PAGE)/MAP_ENTRIES_PER_PAGE)].ppn = BLK_PAGE_NO_SECT(SECTOR(free_blk_no[0], free_page_no[0]));
//写入新的映射表
nand_page_write(SECTOR(free_blk_no[0],free_page_no[0]) & (~OFF_MASK_SECT), copy, 1, 2);
free_page_no[0] += SECT_NUM_PER_PAGE;
}
if(merge_count == 0 )
merge_switch_num++;
else if(merge_count > 0 && merge_count < PAGE_NUM_PER_BLK)
merge_partial_num++;
else if(merge_count == PAGE_NUM_PER_BLK)
merge_full_num++;
else if(merge_count > PAGE_NUM_PER_BLK){
printf("merge_count =%d PAGE_NUM_PER_BLK=%d",merge_count,PAGE_NUM_PER_BLK);
ASSERT(0);
}
nand_erase(victim_blk_no);
return (benefit + 1);
}