Hao Chen

cighao@gmail.com

  • About ME
  • Archives
  • Exploring World
Search

Hao Chen

cighao@gmail.com

  • About ME
  • Archives
  • Exploring World

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

2017-02-27

仍然以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);
}
  • SSD
  • Disksim
  • flashsim

扫一扫,分享到微信

微信分享二维码
在 linux 上首次使用 SSD
disksim-3.0 with flashsim 源码分析(五):写操作

Related Issues not found

Please contact @cighao to initialize the comment

© 2025 Hao Chen
Hexo Theme Yilia by Litten
  • Search

tag:

  • Javascript
  • Web 前端
  • Matlab
  • 遗传算法
  • 算法
  • Hexo
  • 计算机
  • Linux IO
  • Cassandra
  • 数论
  • SSD
  • NVMe
  • Database
  • 论文阅读
  • Disksim
  • flashsim
  • Ubuntu
  • 画图
  • 信号处理
  • 黑客
  • Mysql
  • Python
  • 爬虫
  • 粒子群算法
  • 模拟退火算法
  • Neo4j
  • Ngrok
  • SPDK
  • RocksDB
  • Java
  • Matplotlib
  • openstack swift
  • 分布式存储
  • 对象存储
  • 学术
  • Tool
  • C语言
  • 正则表达式
  • 端口扫描
  • 二层规划
  • 排序
  • 随笔
  • Nodejs
  • Tools
  • 数据库

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录(注意不是yilia根目录)执行以下命令:
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置:

      jsonContent:
        meta: false
        pages: false
        posts:
          title: true
          date: true
          path: true
          text: false
          raw: false
          content: false
          slug: false
          updated: false
          comments: false
          link: false
          permalink: false
          excerpt: false
          categories: false
          tags: true
    

  • 数据库中的热点行优化 (SIGMOD'21 Paper 解读)

    2022-02-28

    #Database#论文阅读

  • NVMe SSD中namespace的介绍和创建

    2020-04-12

    #SSD#NVMe

  • 快速搭建 L2TP VPN 服务器

    2019-11-20

    #计算机#Tool

  • SPDK 介绍(二):SPDK 相关博客

    2019-10-25

    #SPDK

  • SPDK 介绍(一):使用 FIO 测试 SPDK

    2019-10-23

    #SPDK

  • RocksDB 介绍(一):相关博客

    2019-10-22

    #RocksDB

  • Linux IO 相关资料

    2019-09-29

    #计算机#Linux IO

  • Cassandra 介绍(三):Commitlog 介绍(1)

    2019-09-26

    #Cassandra

  • Cassandra 介绍(二):Blogs

    2019-09-22

    #Cassandra

  • Cassandra 介绍(一):Install and test with YCSB

    2019-09-19

    #Cassandra

  • 阿里数据库内核月报(汇总)

    2019-09-03

    #数据库

  • Neo4j 介绍(五):使用 java 访问 neo4j

    2019-04-24

    #Neo4j

  • Neo4j 介绍(四):关于 neo4j 的一些博客

    2019-04-21

    #Neo4j

  • Neo4j 介绍(三):使用 python 访问 neo4j

    2019-04-21

    #Neo4j

  • Neo4j 介绍(二):main 函数

    2019-04-13

    #Neo4j

  • 日常遇到的一些小问题的解决方案

    2019-03-29

    #计算机#Tool

  • Neo4j 介绍(一):安装

    2019-03-21

    #Neo4j

  • matlab 画图(十): 分组和堆叠的条形图

    2019-01-13

    #Matlab#画图

  • 论文写作常用工具

    2018-11-20

    #Tools

  • Openstack Swift学习(八):配置ntp

    2018-09-29

    #openstack swift#分布式存储#对象存储

  • Openstack Swift学习(七):ssbench 使用

    2018-09-29

    #openstack swift#分布式存储#对象存储

  • Openstack Swift学习(六):服务启动源码分析

    2018-09-29

    #openstack swift#分布式存储#对象存储

  • Openstack Swift学习(五):debug 总结

    2018-09-29

    #openstack swift#分布式存储#对象存储

  • Openstack Swift学习(四):中间件

    2018-09-29

    #openstack swift#分布式存储#对象存储

  • Openstack Swift学习(三):log 配置

    2018-09-22

    #openstack swift#分布式存储#对象存储

  • Openstack Swift学习(二):相关文档

    2018-07-20

    #openstack swift#分布式存储#对象存储

  • Openstack Swift学习(一):安装

    2018-07-12

    #openstack swift#分布式存储#对象存储

  • 在 linux 上首次使用 SSD

    2017-03-20

    #SSD

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

    2017-02-27

    #SSD#Disksim#flashsim

  • disksim-3.0 with flashsim 源码分析(五):写操作

    2017-02-27

    #SSD#Disksim#flashsim

  • disksim-3.0 with flashsim 源码分析(四):初始化

    2017-02-27

    #SSD#Disksim#flashsim

  • disksim-3.0 with flashsim 源码分析(三):callFsim()函数介绍

    2017-02-21

    #SSD#Disksim#flashsim

  • disksim-3.0 with flashsim 源码分析(二):DFTL 中的 cache

    2016-12-10

    #SSD#Disksim#flashsim

  • disksim-3.0 with flashsim 源码分析(一):disksim-3.0 和 flashsim 的安装

    2016-12-06

    #SSD#Disksim#flashsim

  • flashsim 源码分析(五): flashsim 的初始化

    2016-11-22

    #SSD#flashsim

  • flashsim 源码分析(四): 总线上锁机制的实现

    2016-11-13

    #SSD#flashsim

  • flashsim 源码分析(三): 总线通道中的交叉

    2016-11-11

    #SSD#flashsim

  • flashsim 源码分析(二): flashsim 中的面向对象设计

    2016-11-09

    #SSD#flashsim

  • flashsim 源码分析(一):安装 flashsim

    2016-11-08

    #SSD#flashsim

  • 利用概率算法求解八皇后问题

    2016-10-20

    #算法

  • 回溯法求解八皇后问题

    2016-10-20

    #算法

  • 利用概率算法估算集合大小

    2016-10-17

    #算法

  • 神奇的卡特兰数

    2016-10-07

    #算法#数论

  • 论文阅读:基于闪存的缓冲区管理算法

    2016-08-23

    #SSD#论文阅读#学术

  • 论文阅读:针对闪存的成本感知的缓冲区管理策略(DASFAA 2015)

    2016-08-19

    #SSD#论文阅读#学术

  • 暴力破解 wifi 密码

    2016-08-04

    #黑客

  • 论文阅读:SSD内部多级并行性的探索和利用(TOC 2013)

    2016-07-20

    #SSD#论文阅读#学术

  • 论文阅读:SSD中基于PSO的缓冲区管理算法(ICITCS 2015)

    2016-07-19

    #SSD#论文阅读#学术

  • 利用二级指针删除链表节点

    2016-07-09

    #算法

  • 抓包获取简书的登录密码

    2016-07-07

    #黑客

  • disksim with ssdmodel 源码解析(二十二):读写和擦除时间的计算

    2016-06-28

    #SSD#Disksim

  • 求离散采样信号的波峰和波谷

    2016-05-31

    #信号处理

  • matlab 画图(九): 横坐标标签倾斜设置

    2016-05-13

    #Matlab#画图

  • matlab 画图(八): 双坐标绘图

    2016-04-29

    #Matlab#画图

  • matlab 画图(七): 扇形图

    2016-04-24

    #Matlab#画图

  • matlab 画图(六): 横向柱状图

    2016-04-20

    #Matlab#画图

  • matlab 画图(五): 垂直柱状图

    2016-04-17

    #Matlab#画图

  • matlab 画图(四): 句柄作图示例

    2016-04-16

    #Matlab#画图

  • disksim with ssdmodel 源码解析(二十一):warm up ssd

    2016-04-15

    #SSD#Disksim

  • matlab 画图(三): 图形句柄

    2016-04-14

    #Matlab#画图

  • matlab 画图(二): 基本作图技巧

    2016-04-13

    #Matlab#画图

  • disksim with ssdmodel 源码解析(二十):统计结果的提取

    2016-04-12

    #SSD#Disksim

  • matlab 画图(一): 线条样式设计

    2016-04-11

    #Matlab#画图

  • disksim with ssdmodel 源码解析(十九):ssd 的初始化

    2016-03-31

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(十八):GC 分析(五)

    2016-03-30

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(十七):GC 分析(四)

    2016-03-30

    #SSD#Disksim

  • SSD 编程学习笔记(一)

    2016-03-29

    #SSD

  • disksim with ssdmodel 源码解析(十六):GC 分析(三)

    2016-03-29

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(十五):GC 分析(二)

    2016-03-27

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(十四):ssd_activate_elem函数分析

    2016-03-24

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(十三):如何兼容64位系统

    2016-03-23

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(十二):写操作分析

    2016-03-23

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(十一):地址映射

    2016-03-23

    #SSD#Disksim

  • matplotlib 画图(四):text 和 label 的设置

    2016-03-22

    #画图#Matplotlib

  • disksim with ssdmodel 源码解析(十):GC分析(一)

    2016-03-19

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(九):syssim_driver 系统级接口(二)

    2016-03-19

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(八):syssim_driver 系统级接口(一)

    2016-03-19

    #SSD#Disksim

  • matplotlib 画图(三):线的连续与间断

    2016-03-19

    #画图#Matplotlib

  • disksim with ssdmodel 源码解析(七):block的组织形式

    2016-03-18

    #SSD#Disksim

  • matplotlib 画图(二):图形填充

    2016-03-17

    #画图#Matplotlib

  • disksim with ssdmodel 源码解析(六):disksim_setup_disksim

    2016-03-16

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(五):程序流程介绍

    2016-03-16

    #SSD#Disksim

  • matplotlib 画图(一):横向柱状图

    2016-03-16

    #画图#Matplotlib

  • 一种时间复杂度为 O(N) 整数排序算法

    2016-03-15

    #算法#排序

  • disksim with ssdmodel 源码解析(四):ssd_event_arrive 函数的介绍

    2016-03-13

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(三):初次使用介绍

    2016-03-12

    #SSD#Disksim

  • disksim with ssdmodel 源码解析(二):输入参数的介绍

    2016-03-06

    #SSD#Disksim

  • 在 Hexo 中给文章添加版权信息

    2016-03-01

    #Hexo

  • python中的爬虫神器 XPath 介绍

    2016-03-01

    #Python#爬虫

  • 程序员得长多高

    2016-02-26

    #Python#爬虫#随笔

  • Hexo 博客添加打赏功能

    2016-02-23

    #Hexo

  • Hexo 主题优化

    2016-02-14

    #Hexo

  • 利用 HttpClient 刷 CSDN 博客文章浏览量

    2016-02-04

    #Java

  • nodejs 中模块使用的介绍

    2016-01-10

    #Nodejs

  • 利用 javascript 实现回到顶部效果

    2016-01-09

    #Javascript#Web 前端

  • Ngrok: 一个提供内网到外网映射的工具

    2015-12-18

    #Ngrok

  • 如何给数百万考生的成绩排序

    2015-12-17

    #算法#排序

  • 在 Hexo 中给文章添加目录

    2015-12-13

    #Hexo

  • Java 动态加载类

    2015-12-06

    #Java

  • python 中安装 requests 模块

    2015-12-05

    #Python#爬虫

  • 利用模拟退火算法求解TSP问题

    2015-12-04

    #算法#模拟退火算法

  • 模拟退火算法简介

    2015-12-03

    #算法#模拟退火算法

  • 粒子群优化算法简介

    2015-11-30

    #算法#粒子群算法

  • Hexo yilia主题添加网站访客人数统计

    2015-11-30

    #Hexo

  • 利用粒子群算法求解非线性二层规划问题

    2015-11-07

    #算法#粒子群算法#二层规划

  • 遗传算法的 matlab 实现

    2015-11-03

    #Matlab#遗传算法#算法

  • 基于javascript实现的2048小游戏

    2015-11-02

    #Javascript#Web 前端

  • 随机生成正整数 1-n 的一个排列

    2015-10-11

    #算法#C语言

  • disksim with ssdmodel 源码解析(一):disksim及ssdmodel模块扩展的安装

    2015-09-09

    #SSD#Disksim#Ubuntu

  • 固态硬盘(SSD)原理及相关介绍

    2015-08-31

    #SSD

  • windows7下安装ubuntu及相关问题的解决方案

    2015-08-27

    #Ubuntu

  • python 正则表达式的使用

    2015-08-22

    #Python#爬虫#正则表达式

  • 基于 python socket 的端口扫描程序

    2015-03-29

    #Python#端口扫描

  • mysql windows 下zip安装

    2015-03-29

    #Mysql