DFTL源码阅读1

发表于 | 阅读次数:

DFTL源码阅读笔记(1)

DFTL算法举例理解

在理解代码前，首先理解下面关于DFTL的一个例子的示意图十分必要：

首先理解CMT和GTD，在DFTL中，经常访问的LPN-PPN这个映射关系是缓存到RAM/DRAM中的，全部的映射关系是存放在flash内部的一小块区域（这里图示为翻译块区域），其中LPN-PPN这个简单的映射关系一般是4byte，而一个数据页大概是2048byte大小。也就是一个数据页（翻译页）可以存放大概512的映射关系。但是要知道这些翻译页在flash的位置，则需要GTD来管理对应的MVPN–>MPPN的关系。

那现在需要捋下DLPN，DPPN，MVPN，MPPN的关系了

  1. DLPN：也是我们理解的host发送请求的逻辑页地址
  2. DPPN：对应的DLPN在flash中存放的物理页地址
  3. MVPN：虚拟页的编号（地址）–这个编号和DLPN存在固定的关系，DLPN/512(如果页的大小是2K）得到的商，就是该DLPN所属的MVPN
  4. MPPN:就是实际存放映射表的物理页地址。需要注意的是，只要该翻译页512项的中的一项关系发生改变，就要异地更新到其他空闲页位置上。

举个例子吧，1G的flash(全部都是数据区域，不考虑翻译区域），按照4个扇区一页（2K），大概有524288个数据页，即存在524288个映射关系，一个2k的数据页大概可以存放512个映射关系，那么就需要1024个翻译页，也就是MVPN的编号从0-1023结束(GTD需要加载的项)，如果按块包含64个页的话，就需要16个底层的块作为翻译块。

在就上图DFTL的请求处理机制进行理解，当DLPN=1280到来的时候，此时的CMT的列表项是满的，根据一定规则（DFTL采用的是S-LRU的原则），选择剔除的对象。这里选中DLPN=1–>DPPN=260的映射项作为剔除对象，剔除的时候需要检测该映射关系是否和flash中存的翻译页中的映射关系是否同步（一般不同步），不同步则异地更新，同时更新需要注意更新对应的GTD的关系。

根据DLPN=1,查找对应的MVPN=(int）DLPN/512=0,也就是MVPN=0,根据GTD的映射表，找到对应的MPPN=21,此时访问读取MPPN=21中的数据，异地更新对应的数据到MPPN=23上，同时更新对应GTD中的翻译页的映射关系MVPN=0—>MPPN=23。将DLPN的映射关系加载到CMT中，也需要找到对应的MVPN=DLPN/512=2,根据GTD查找MVPN=2对应的翻译页物理地址是MPPN=15，在这个翻译页中找到对应的映射关系DLPN=1280—>DPPN=660，加载这个映射项到CMT中，同时根据这个映射关系，可以访问DPPN=660数据，如果数据发生了更新，则修改CMT中DLPN—>DPPN的映射关系。

源码解析

在介绍初始化函数之前，有必要先知道dftl.c/.h中涉及的自定义结构体opagemap和mapdir：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct opm_entry {
  _u32 free  : 1;
  _u32 ppn   : 31;
  int  cache_status;
  int  cache_age;
  int  map_status;
  int  map_age;
  int  update;
};

struct opm_entry *opagemap;

struct omap_dir{
  unsigned int ppn;
};
struct omap_dir *mapdir;

opagemap 是opm_entry的结构体指针，opagemap[X].ppn就完成了DLPN–>DPPN的一组映射关系，X表示DLPN，ppn就是我们理解的DPPN
而omap_dir实际就是一个int类型的数组，mapdir[X].ppn也完成了MVPN（X）—> MPPN（ppn）的一组映射关系
先从初始化函数入手：

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
函数输入的blk_num表示数据块的个数，extra_num表示空闲块的个数
int opm_init(blk_t blk_num, blk_t extra_num)
{
  int i;
  int mapdir_num;//mapdir_num表示的是GTD中的映射个数

  opagemap_num = blk_num * PAGE_NUM_PER_BLK;//opagemap_num表示全部的映射关系:DLPN--->DPPN

  //create primary mapping table
  opagemap = (struct opm_entry *) malloc(sizeof (struct opm_entry) * opagemap_num);

  mapdir = (struct omap_dir *)malloc(sizeof(struct omap_dir) * opagemap_num / MAP_ENTRIES_PER_PAGE); 

  if ((opagemap == NULL) || (mapdir == NULL)) {
    return -1;
  }

 //mapdir_num表示的是GTD中MVPN-->MPPN的映射项个数
  mapdir_num = (opagemap_num / MAP_ENTRIES_PER_PAGE);

//也可能出现映射关系项不能被512整除的情况，额外多分配一个翻译页
  if((opagemap_num % MAP_ENTRIES_PER_PAGE) != 0){
    printf("opagemap_num % MAP_ENTRIES_PER_PAGE is not zero\n"); 
    mapdir_num++;
  }

  memset(opagemap, 0xFF, sizeof (struct opm_entry) * opagemap_num);
  memset(mapdir,  0xFF, sizeof (struct omap_dir) * mapdir_num);

  //youkim: 1st map table 
  TOTAL_MAP_ENTRIES = opagemap_num;

  for(i = 0; i<TOTAL_MAP_ENTRIES; i++){
    opagemap[i].cache_status = 0;
    opagemap[i].cache_age = 0;
    opagemap[i].map_status = 0;
    opagemap[i].map_age = 0;
    opagemap[i].update = 0;
  }

  extra_blk_num = extra_num;
//因为更新的时候，分为数据项更新和翻译地址更新，所以需要在存在两个当前空闲的块位置，一个为即将更新的数据准备，一个为地址更新准备
//free_page_no[0]表示当前可写入的映射页的空闲物理地址，free_page_no[1]存放的是当前可以写入的数据页的空闲物理地址页。
//free_blk_no[0]存的是当前可写入映射项的物理块地址，free_page_no[1]存放的是当前可以写入的数据页的物理块地址
  free_blk_no[0] = nand_get_free_blk(0);
  free_page_no[0] = 0;
  free_blk_no[1] = nand_get_free_blk(0);
  free_page_no[1] = 0;

  //initialize variables
  MAP_REAL_NUM_ENTRIES = 0;
  MAP_GHOST_NUM_ENTRIES = 0;
  CACHE_NUM_ENTRIES = 0;
  SYNC_NUM = 0;

  cache_hit = 0;
  flash_hit = 0;
  disk_hit = 0;
  evict = 0;
  read_cache_hit = 0;
  write_cache_hit = 0;
  write_count =0;
  read_count = 0;
  save_count = 0;

//更新全局的GTD的初始化，调用了opm_write最后一个参数是2表示更新的是翻译页操作
  //update 2nd mapping table
  for(i = 0; i<mapdir_num; i++){
    ASSERT(MAP_ENTRIES_PER_PAGE == 512);
    opm_write(i*SECT_NUM_PER_PAGE, SECT_NUM_PER_PAGE, 2);
  }

  /*
  for(i = mapdir_num; i<(opagemap_num - mapdir_num - (extra_num * PAGE_NUM_PER_BLK)); i++){
    opm_write(i*SECT_NUM_PER_PAGE, SECT_NUM_PER_PAGE, 1);
  }
  */

  // update dm_table
  /*
  int j;
  for(i = mapdir_num; i<(opagemap_num - mapdir_num - (extra_num * PAGE_NUM_PER_BLK)); i++){
      for(j=0; j < SECT_NUM_PER_PAGE;j++)
        dm_table[ (i*SECT_NUM_PER_PAGE) + j] = DEV_FLASH;
  }
  */
  
  return 0;
}

这里还是没有搞懂，opagemap_num表示的是所有的块（翻译块+数据块）的个数还是单纯的数据快的个数（下面的代码理解可以确定是所有块个数），查看调用的opm_write函数
输入参数lsn表示请求的扇区号，size请求大小（以扇区为单位），mapdir_flag=2表示操作的是翻译页，mapdir_flag=1操作的是数据页
因为底层的nand一个物理扇区存的数据其实就是实际对应的lsn，所以会有在函数中定义lsns数组，将lsns设置好的数据按一个页的扇区大小回写到底层的nand。

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
size_t opm_write(sect_t lsn, sect_t size, int mapdir_flag)  
{
  int i;
  int lpn = lsn/SECT_NUM_PER_PAGE; // logical page number
  int size_page = size/SECT_NUM_PER_PAGE; // size in page 
  int ppn;
  int small;
  //small这个标识符就是根据输入参数的mapdir-flag设置的，0:表示操作映射项：1:表示操作数据项，这里是为了结合上面的中free_page_no做指定下标的，free_page_no[0]表示当前可写入的映射页的空闲物理地址，free_page_no[1]存放的是当前可以写入的数据页的空闲物理地址页。

  sect_t lsns[SECT_NUM_PER_PAGE];
  int sect_num = SECT_NUM_PER_PAGE;

  sect_t s_lsn;	// starting logical sector number
  sect_t s_psn; // starting physical sector number 
  sect_t s_psn1;


  ASSERT(lpn < opagemap_num);
  ASSERT(lpn + size_page <= opagemap_num);

  s_lsn = lpn * SECT_NUM_PER_PAGE;


  if(mapdir_flag == 2) //map page
    small = 0;
  else if ( mapdir_flag == 1) //data page
    small = 1;
  else{
    printf("something corrupted");
    exit(0);
  }

//free_page_no[small]实际存放的是扇区号，如果当前的扇区地址超出了一个块包含的扇区数，则表示该物理块耗尽，
//那么也可以理解其实这个扇区号是相对于这个块的偏移量
  if (free_page_no[small] >= SECT_NUM_PER_BLK) 
  {
	//如果找不到对应的空块则启用相应的垃圾回收，可以看到其中的free_blk_no[0/1]存的是物理块地址
    if ((free_blk_no[small] = nand_get_free_blk(0)) == -1) 
    {
      int j = 0;

      while (free_blk_num < 3 ){
        j += opm_gc_run(small, mapdir_flag);
      }
      opm_gc_get_free_blk(small, mapdir_flag);
    } 
    else {
      free_page_no[small] = 0;
    }
  }

  memset (lsns, 0xFF, sizeof (lsns));
  //s_psn是用物理块号+块内的扇区偏移量构成的实际物理扇区地址（高8位地址是块号，后面的是块内扇区偏移量）
  s_psn = SECTOR(free_blk_no[small], free_page_no[small]);

  if(s_psn % 4 != 0){
    printf("s_psn: %d\n", s_psn);
  }

//ppn是物理页地址号，其高8位也是物理块号，去掉块号后几位就是块内的页偏移量
  ppn = s_psn / SECT_NUM_PER_PAGE;
//依据opagemape[lpn].ppn的映射关系，找到之前的物理扇区起始地址（页地址），将其置为无效
  if (opagemap[lpn].free == 0) {
  //free=0表示对应的地址ppn中存了数据
    s_psn1 = opagemap[lpn].ppn * SECT_NUM_PER_PAGE;
    //注意底层的nand的置位都是按扇区操作的
    for(i = 0; i<SECT_NUM_PER_PAGE; i++){
      nand_invalidate(s_psn1 + i, s_lsn + i);
    } 
    nand_stat(3);
  }
  else {
  //没有存数据，则将其free置位，之后写入数据
    opagemap[lpn].free = 0;
  }

  for (i = 0; i < SECT_NUM_PER_PAGE; i++) 
  {
    lsns[i] = s_lsn + i;
  }

//从这段代码可以理解了opagemap_num表示所有的页（翻译页+数据页）
//绑定新的ppn，如果操作的是映射项，还需要更新对应的mapdir[lpn].ppn
  if(mapdir_flag == 2) {
    mapdir[lpn].ppn = ppn;
    opagemap[lpn].ppn = ppn;
  }
  else {
    opagemap[lpn].ppn = ppn;
  }
//当前对应可以写入的空闲扇区标识向后移动
  free_page_no[small] += SECT_NUM_PER_PAGE;

//之后就是依据指定的物理扇区地址和逻辑扇区地址进行写入操作
  nand_page_write(s_psn, lsns, 0, mapdir_flag);

  return sect_num;
}

opm_write的代码逻辑可以简要概括为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
graph TD;
	A[请求到来]-->B[辨别操作date/Map:mapdir_flag=1/2];
	B-->|data|C[small=1];
	B-->|map|D[small=0];
	C-->E[需要注意的是free_page_no-small存的都是扇区地址,free_blk_no-small存的都是当前可以写入的物理块地址];
	D-->E;
	E-->|free_page_no大于块内包含扇区数SECT_NUM_PER_BLK|F;
	F[调用nand_get_free_blk得新的空闲物理块]
	F-->|free_blk_num小于指定的最小块数|K[调用opm_gc_run opm_gc_get_free_blk函数进行垃圾回收];
	E-->|free_page_no小于等于SECT_NUM_PER_BLK|G;
	G[根据物理块号和块内偏移量计算得到物理页号ppn 物理扇区号s_psn];
	K-->G;
	G-->I;
	I[opagemape-lpn.ppn映射关系的更新]
	I-->H;
	H[如果opagemap-lpn.free不为0表示存在数据,则调用相应的nand_invalid函数将原来的数据置位无效,原物理地址来自opagemape-lpn.ppn]
	H-->h[如果mapdir_flag为2,同时更新mapdir-lpn.ppn为当前分配的ppn]
	h-->i
	i[最后调用nand_page_write函数按照制定的s_psn,lsn,map_dir_flag进行写入操作]
	i-->e;
	e[函数最后返回的是操作的扇区大小sect_num];

可以发现opm_write()函数与其他几个函数发生了调用关系：

1
2
3
4
5
6
7
graph LR;
	A[opm_write];
	A-->B[opm_gc_run];
	A-->C[opm_gc_get_free_blk];
	A-->F[nand_get_free_blk]
	A-->D[nand_invalidate];
	A-->E[nand_page_write];

下面结合nand_page_write()函数查看针对map和data底层的nand是怎么处理的 ？？
唯一的区别只是底层的nand_blk[pbn].page_status对应的扇区1表示map，0表示data

1
2
3
4
5
6
7
8
9
10
第三个参数isGC表示当前的flash是否在执行垃圾回收操作
_u8 nand_page_write(_u32 psn, _u32 *lsns, _u8 isGC, int map_flag)
//关键的代码段针对map_flag的处理
//唯一的区别只是底层的nand_blk[pbn].page_status对应的扇区1表示map，0表示data
  if(map_flag == 2) {
        nand_blk[pbn].page_status[pin/SECT_NUM_PER_PAGE] = 1; // 1 for map table
  }
  else{
    nand_blk[pbn].page_status[pin/SECT_NUM_PER_PAGE] = 0; // 0 for data 
  }

需要理解后面的关于opm_gc_run和opm_gc_get_free_blk函数，但是
opm_gc_run选择回收的块时调用了opm_gc_cost_benefit()选择合适的块进行垃圾回收，因此从opm_gc_cost_benefit()进行着手

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
_u32 opm_gc_cost_benefit()
{
  int max_cb = 0;
  int blk_cb;

  _u32 max_blk = -1, i;
//避免选择的回收的块是刚刚更新完的数据块或者翻译块
  for (i = 0; i < nand_blk_num; i++) {
    if(i == free_blk_no[0] || i == free_blk_no[1]){
      continue;
    }

//通过下面这个代码逻辑可以确定，opm_gc_cost_benefit函数是选择无效页最多的块进行回收的
    blk_cb = nand_blk[i].ipc;

    
    if (blk_cb > max_cb) {
      max_cb = blk_cb;
      max_blk = i;
    }
  }

  ASSERT(max_blk != -1);
  ASSERT(nand_blk[max_blk].ipc > 0);
  return max_blk;
}

同时还会牵扯调用函数opm_gc_get_free_blk函数

1
2
3
4
5
6
7
8
9
10
11
12
13
int opm_gc_get_free_blk(int small, int mapdir_flag)
{
  if (free_page_no[small] >= SECT_NUM_PER_BLK) {

    free_blk_no[small] = nand_get_free_blk(1);

    free_page_no[small] = 0;

    return -1;
  }
  
  return 0;
}

opm_gc_get_free_blk函数只是简单地判断free_page_no[small] 超出 SECT_NUM_PER_BLK，如果超出了就简单调用nand_get_free_blk(1)函数。这里又涉及到底层的nand_get_free_blk函数，在这也顺便捋清楚，过一遍选择可用块的时候都是选择被擦除次数最少的块进行利用，输入参数isGC是为了结合当前空余块数是否小于阈值，启用相应的垃圾回收（如果函数返回-1表示没有相应的空块可以利用）。

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
_u32 nand_get_free_blk (int isGC) 
{
  _u32 blk_no = -1, i;
  int flag = 0,flag1=0;
  flag = 0;
  flag1 = 0;

  MIN_ERASE = 9999999;
  //in case that there is no avaible free block -> GC should be called !
  if ((isGC == 0) && (min_fb_num >= free_blk_num)) {
    //printf("min_fb_num: %d\n", min_fb_num);
    return -1;
  }

  for(i = 0; i < nand_blk_num; i++) 
  {
    if (nand_blk[i].state.free == 1) {
      flag1 = 1;

      if ( nand_blk[i].state.ec < MIN_ERASE ) {
            blk_no = i;
            MIN_ERASE = nand_blk[i].state.ec;
            flag = 1;
      }
    }
  }
  if(flag1 != 1){
    printf("no free block left=%d",free_blk_num);
    
  ASSERT(0);
  }
  if ( flag == 1) {
        flag = 0;
        ASSERT(nand_blk[blk_no].fpc == SECT_NUM_PER_BLK);
        ASSERT(nand_blk[blk_no].ipc == 0);
        ASSERT(nand_blk[blk_no].lwn == -1);
        nand_blk[blk_no].state.free = 0;

        free_blk_idx = blk_no;
        free_blk_num--;

        return blk_no;
  }
  else{
    printf("shouldn't reach...\n");
  }

  return -1;
}

opm_gc_cost_benefit()在进行垃圾回收选择块时，避免选择刚刚更新的数据块和翻译块，而是选择包含无效页最多的块进行回收。
opm_gc_run函数的输入参数small：0/1(Map/data），mapdir-flag:2/1(Map/data)
代码里面的涉及的位运算在这里进行初步讲解：
#define OFF_MASK_SECT 0x00000003
#define OFF_F_SECT(sect) (((sect) & OFF_MASK_SECT))
利用OFF_F_SECT函数就可以得到后三位的数据（也就是0-255的值），一个块内包含的扇区数（指定物理块内的扇区偏移量）
#define PAGE_SECT_BITS 8
#define SECTOR(blk, page) (((blk) << PAGE_SECT_BITS) | (page))
这个宏做的工作就是将物理块号和块内偏移量组合得到物理页号
#define SECT_BITS 2
#define BLK_PAGE_NO_SECT(sect) ((sect) >> SECT_BITS)
这里有必要说明一点传入参数的s_psn这些逻辑扇区地址实际上是这样一个编码（物理编号）+（块内页偏移量）+（页内偏移量）
相当于直接去掉编码后两位中关于扇区的编号，只存在块编号和页编号
#define OFF_MASK_SECT 0x00000003

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
162
163
164
165
166
167
168
169
int opm_gc_run(int small, int mapdir_flag)
{
  blk_t victim_blk_no;
  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();
  memset(copy_lsn, 0xFF, sizeof (copy_lsn));
//free_page_no里面存的物理扇区号=物理块+块内的扇区偏移量，OFF_F_SECT是得到块内的扇区偏移量
  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){ //map block
      for( q = 0; q  < 64; q++) {
        if(nand_blk[victim_blk_no].page_status[q] == 0 ){
          printf("something corrupted1=%d",victim_blk_no);
        }
      }
      small = 0;
      break;
    } 
    else if(nand_blk[victim_blk_no].page_status[q] == 0){ //data block
      for( q = 0; q  < 64; q++) {
        if(nand_blk[victim_blk_no].page_status[q] == 1 ){
          printf("something corrupted2",victim_blk_no);
        }
      }
      small = 1;
      break;
    }
  }

  ASSERT ( small == 0 || small == 1);
  pos = 0;
  merge_count = 0;
  //无论回收的是数据块还是翻译块都需要回收有效页
  for (i = 0; i < PAGE_NUM_PER_BLK; i++) 
  {
	//依次便利块中的数据页，查看数据是否有效
    valid_flag = nand_oob_read( SECTOR(victim_blk_no, i * SECT_NUM_PER_PAGE));

    if(valid_flag == 1)
    {
        valid_sect_num = nand_page_read( SECTOR(victim_blk_no, i * SECT_NUM_PER_PAGE), copy, 1);

        merge_count++;
//copy_lsn和copy存放的都是相应的有效扇区的数据（其实就是逻辑扇区号lsn）
        ASSERT(valid_sect_num == 4);
        k=0;
        for (j = 0; j < valid_sect_num; j++) {
          copy_lsn[k] = copy[j];
          k++;
        }
//调用opm_gc_get_free_blk就是为相应的空闲新的块，来存数据(映射关系）
          benefit += opm_gc_get_free_blk(small, mapdir_flag);

          if(nand_blk[victim_blk_no].page_status[i] == 1)
          {     
//如果回收的是翻译页，同时要更新对应的mapdir页映射（GTD）的关系MVPN---->MPPN，这里的S值就是0,在上面有过判断`printf("s && k should be 0\n");`
//(copy_lsn[s]/SECT_NUM_PER_PAGE)就是有效页对应的逻辑页地址DLPN，如果是有效的翻译页就是DVPN
            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最后一个参数是mapdir_flag,主要影响nand_blk[pbn].page_status[offset]=0/1(data/map）
            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]));
//SECTOR(free_blk_no[small],free_page_no[small]) & (~OFF_MASK_SECT)的值是扇区的对应页的起始地址
            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;
//如果对应的数据项在gc中发生了异地更新，碰巧其映射项存在cache中（CMT中），那就需要记录不同步的个数 delay_flash_update
            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++;
            }    
            else {
  //反之将写入的扇区（逻辑扇区号）存到map-arr中，s，k就是0,map_arr[pos]，copy_lsn[s]都是该页起始的扇区地址
              map_arr[pos] = copy_lsn[s];
              pos++;
            } 
          }
    }
  }
//初始化temp_arr数组
  for(i=0;i < PAGE_NUM_PER_BLK;i++) {
      temp_arr[i]=-1;
  }
  k=0;
  
//下面这段就是找到映射关系不存在CMT中的这些数据页的映射关系包含在不同的翻译页中，temp_arr[K]存的就是该翻译页对应的物理页地址，temp_arr1[k]存的是对应的数据页的逻辑扇区（页起始）
  for(i =0 ; i < pos; i++) {
      old_flag = 0;
      for( j = 0 ; j < k; j++) {
	  //其实((map_arr[i]/SECT_NUM_PER_PAGE)/MAP_ENTRIES_PER_PAGE计算得到的就是我们理解的MVPN
           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]表示相应的GTD中的MPPN
           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++;
  }
//数据页对应的映射关系发生了变化，相应的翻译页也需要更新，不存在CMT的翻译页需要更新--->对应的GTD也需要更新
  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);

//更新对应的GTD    MVPN-------------> MPPN
            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对应的映射关系，需要提及的一点在callFsim源码中，针对所有的请求的页地址都做了blkno += page_num_for_2nd_map_table的偏置
            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);
}

OK理解了上面的opm_gc_run函数代码，做一个相关函数调用的示意图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
graph LR;
	A(opm_gc_run);
	B[opm_gc_cost_benefit];
	C[nand_oob_read];
	D[nand_page_read];
	E[opm_gc_get_free_blk];
	F[nand_get_free_blk-1];
	I[nand_invalidate];
	H[nand_page_write];
	A-->|选择无效页最多的块进行回收|B;
	A-->|通过OOB识别回收块中的有效数据|C;
	A-->|读取底层的块的数据|D;
	A-->|为回收的有效页找新的块进行存储|E;
	E-->|只是简单的调用,判断free_page_no-small是否越界,越界就调用|F;
	A-->|将原来的数据页或者翻译页置位无效|I;
	A-->|将新的数据,数据页或者映射关系,翻译页写入nand|H;

此外针对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
graph TD;
	A(opm_gc_run,输入参数small,mapdir_flag);
	Z(程序异常退出);
	B[调用opm_gc_cost_benefit,得到对应的victim_blk_no];
	C{victim_blk_no的page_status?};
	D(无论回收的块是数据块还是翻译块都需要回收块中的有效页);
	E{查看page_status};
	E2(函数最后调用nand_erase,擦除指定的回收块);
	F[回收的是翻译页]
	H[回收的是数据页]
	D1[调用nand_oob_read识别扫描扇区是否存在有效数据];
	D2[调用nand_page_read读取有效扇区的数据,其实存的就是对应的逻辑扇区号];
	D3[调用opm_gc_get_free_blk函数为新的数据页分配新的物理扇区-页地址];
	D4[翻译页更新,需要更新GID,这里修改的是mapdir-lpn.ppn的映射关系,同时需要注意的是也会更新opagemap-lpn.ppn的映射关系]
	N1[需要注意的是在callFsim初始化函数中,针对请求页地址blkno都会有加上page_num_for_2nd_map_table的偏置]
	D5[调用nand_page_write函数将翻译页更新到新的物理地址中];
	
	M1(数据页的回收更新,较为复杂,映射关系发生变化,相应的翻译页也需要更新,同时需要判断映射关系项是否存在CMT中,如果存在CMT,则相应的映射关系延迟更新);
	M2[调用nand_oob_read识别扫描扇区是否存在有效数据];
	M3[调用nand_page_read读取有效扇区的数据,其实存的就是对应的逻辑扇区号];
	M4[调用opm_gc_get_free_blk函数为新的数据页分配新的物理扇区-页地址];
	M5[调用nand_page_write函数将数据页更新到新的物理地址中,开始处理对应的映射关系更新];
	M6{判断该数据页映射项是否存在CMT?};
	M7[延迟更新,delay_flash_update++];
	M8[将这些数据页地址DLPN保存在map_arr数组中,方便后面处理];
	M9(代码中存在处理map_arr的for循环,就是为了分别出这些不存在CMT的映射分别存在那些不同的翻译页中);
	M10(temp_arr-K存的就是该翻译页对应的物理页地址,temp_arr1-k存的是对应的数据页的逻辑扇区-页起始,针对同一翻译页的映射关系累计项存在变量save_count);
	M11[利用temp_arr-K中存放的物理页地址,将这些旧翻译数据页先读取后置位无效];
	M12[更新对应的GTD,同时将修改对应的opagemap对应的映射关系写到新的分配物理地址上];
	
	A-->|选择无效页最多的块进行回收|B;
	B-->C;
	C-->|如果存在数据页和翻译页混在同一块中|Z;
	C-->|块中的页page_status一致|D;
	D-->E;
	E-->|page_status=1|F;
	E-->|page_status=0|H;
	F-->D1;
	D1-->D2;
	D2-->D3;
	D3-->D4;
	D4---N1;
	D4-->D5;
	H-->M1;
	M1-->M2;
	M2-->M3;
	M3-->M4;
	M4-->M5;
	M5-->M6;
	M6-->|存在CMT|M7;
	M6-->|不存在CMT|M8;
	M8---M9;
	M9---M10;
	M10-->M11;
	M11-->M12;
	
	M12-->E2;
	D5-->E2;

热评文章