disksim-3.0 with flashsim 源码分析（六）：垃圾回收

2017-02-27

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

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 操作大致分为以下几个步骤：

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

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

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

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);
}