Cosmos OpenSSD--greedy_ftl1.2.0(三)

我们来假设模拟一个小型的模型来分析写和垃圾回收的过程

假设只有一个die,4个block,每个block4个page,每个page8KB

那么PageMap就是Page[0][0]到Page[0][15]

BlockMap就是Block[0][0]到Block[0][3]

GcMap就是GC[0][0]到GC[0][4]

那么最初就会如下图:第零块用来保留元数据,最后一块保留作为垃圾回收合并块

Cosmos OpenSSD--greedy_ftl1.2.0(三)


接下来从上层来了数据,黄色部分表示更改的数据,红色部分表示更新的数据,最左侧是流程

在这里,lpn0的内容作为page缓存留在SDRAM里面,只把lpn1的内容存入flash

Cosmos OpenSSD--greedy_ftl1.2.0(三)


接下来更改的数据缓存命中了,所以lpn0的内容直接在SDRAM里面修改,此时数据末尾刚好占据了一个页,所以直接存入flash,并把之前的保存页无效,此时GC表开始变化

Cosmos OpenSSD--greedy_ftl1.2.0(三)


接下来依旧缓存命中,但是请求最后一页并不是完整的一页,于是先预读出其中的内容,修改之后寻找新页再保存进flash

Cosmos OpenSSD--greedy_ftl1.2.0(三)


这一次的缓存并没有命中,所以先把SDRAM里面的内容flush进SDRAM里面,因为请求并不满足一页,所以执行read-modify-write,此时lpn1作为新的page缓存,并不直接存进flash而是保留在SDRAM中

Cosmos OpenSSD--greedy_ftl1.2.0(三)


缓存依旧不命中,此时block1已经没有页面可用了,于是找到了下一个空闲block,先flush,然后更新page缓存,将lpn1的内容存入flash

Cosmos OpenSSD--greedy_ftl1.2.0(三)


接下来缓存不命中,并且消耗掉了所有的页面,于是lpn3的内容无处存取,引发垃圾回收操作

Cosmos OpenSSD--greedy_ftl1.2.0(三)


垃圾回收操作的依据是元数据的更新,因此我们来看元数据更新的代码

 void UpdateMetaForOverwrite(u32 lpn)
{
pageMap = (struct pmArray*)(PAGE_MAP_ADDR);
blockMap = (struct bmArray*)(BLOCK_MAP_ADDR);
gcMap = (struct gcArray*)(GC_MAP_ADDR); u32 dieNo = lpn % DIE_NUM;
u32 dieLpn = lpn / DIE_NUM; if(pageMap->pmEntry[dieNo][dieLpn].ppn != 0xffffffff)
{
// GC victim block list management
u32 diePbn = pageMap->pmEntry[dieNo][dieLpn].ppn / PAGE_NUM_PER_BLOCK; // unlink
if((blockMap->bmEntry[dieNo][diePbn].nextBlock != 0xffffffff) && (blockMap->bmEntry[dieNo][diePbn].prevBlock != 0xffffffff))
{
blockMap->bmEntry[dieNo][blockMap->bmEntry[dieNo][diePbn].prevBlock].nextBlock = blockMap->bmEntry[dieNo][diePbn].nextBlock;
blockMap->bmEntry[dieNo][blockMap->bmEntry[dieNo][diePbn].nextBlock].prevBlock = blockMap->bmEntry[dieNo][diePbn].prevBlock;
}
else if((blockMap->bmEntry[dieNo][diePbn].nextBlock == 0xffffffff) && (blockMap->bmEntry[dieNo][diePbn].prevBlock != 0xffffffff))
{
blockMap->bmEntry[dieNo][blockMap->bmEntry[dieNo][diePbn].prevBlock].nextBlock = 0xffffffff;
gcMap->gcEntry[dieNo][blockMap->bmEntry[dieNo][diePbn].invalidPageCnt].tail = blockMap->bmEntry[dieNo][diePbn].prevBlock;
}
else if((blockMap->bmEntry[dieNo][diePbn].nextBlock != 0xffffffff) && (blockMap->bmEntry[dieNo][diePbn].prevBlock == 0xffffffff))
{
blockMap->bmEntry[dieNo][blockMap->bmEntry[dieNo][diePbn].nextBlock].prevBlock = 0xffffffff;
gcMap->gcEntry[dieNo][blockMap->bmEntry[dieNo][diePbn].invalidPageCnt].head = blockMap->bmEntry[dieNo][diePbn].nextBlock;
}
else
{
gcMap->gcEntry[dieNo][blockMap->bmEntry[dieNo][diePbn].invalidPageCnt].head = 0xffffffff;
gcMap->gcEntry[dieNo][blockMap->bmEntry[dieNo][diePbn].invalidPageCnt].tail = 0xffffffff;
} // xil_printf("[unlink] dieNo = %d, invalidPageCnt= %d, diePbn= %d, blockMap.prevBlock= %d, blockMap.nextBlock= %d, gcMap.head= %d, gcMap.tail= %d\r\n", dieNo, blockMap->bmEntry[dieNo][diePbn].invalidPageCnt, diePbn, blockMap->bmEntry[dieNo][diePbn].prevBlock, blockMap->bmEntry[dieNo][diePbn].nextBlock, gcMap->gcEntry[dieNo][blockMap->bmEntry[dieNo][diePbn].invalidPageCnt].head, gcMap->gcEntry[dieNo][blockMap->bmEntry[dieNo][diePbn].invalidPageCnt].tail); // invalidation update
pageMap->pmEntry[dieNo][pageMap->pmEntry[dieNo][dieLpn].ppn].valid = ;
blockMap->bmEntry[dieNo][diePbn].invalidPageCnt++; // insertion
if(gcMap->gcEntry[dieNo][blockMap->bmEntry[dieNo][diePbn].invalidPageCnt].tail != 0xffffffff)
{
blockMap->bmEntry[dieNo][diePbn].prevBlock = gcMap->gcEntry[dieNo][blockMap->bmEntry[dieNo][diePbn].invalidPageCnt].tail;
blockMap->bmEntry[dieNo][diePbn].nextBlock = 0xffffffff;
blockMap->bmEntry[dieNo][gcMap->gcEntry[dieNo][blockMap->bmEntry[dieNo][diePbn].invalidPageCnt].tail].nextBlock = diePbn;
gcMap->gcEntry[dieNo][blockMap->bmEntry[dieNo][diePbn].invalidPageCnt].tail = diePbn;
}
else
{
blockMap->bmEntry[dieNo][diePbn].prevBlock = 0xffffffff;
blockMap->bmEntry[dieNo][diePbn].nextBlock = 0xffffffff;
gcMap->gcEntry[dieNo][blockMap->bmEntry[dieNo][diePbn].invalidPageCnt].head = diePbn;
gcMap->gcEntry[dieNo][blockMap->bmEntry[dieNo][diePbn].invalidPageCnt].tail = diePbn;
}
}
}

其实从上面的写过程分析,我们可以大概了解到GC表其实就是把有相同无效页的block串联在一起

我们假设从block1到block7,其中无效页最终分别为100,120,110,100,110,120,100

当block1进行完之后,GC[0][100].head=1  GC[0][100].tail=1

当block2的无效页也到达100的时候,分析代码可知,GC[0][100].head=1  GC[0][100].tail=2,而且block1和block2会链接起来,但是block2的无效页会继续增加,于是当他的无效页增加的时候,block1和block2又会断开,指向无效的0xffffffff,而block2执行完毕之后GC[0][120].head=2  GC[0][120].tail=2.

只有当block4和block7的无效页最终停在100的时候,block1↔block4↔block7


既然已经了解GC表表示的什么意思,那么再看垃圾回收操作的代码就简单多了

 u32 GarbageCollection(u32 dieNo)
{
xil_printf("GC occurs!\r\n"); pageMap = (struct pmArray*)(PAGE_MAP_ADDR);
blockMap = (struct bmArray*)(BLOCK_MAP_ADDR);
dieBlock = (struct dieArray*)(DIE_MAP_ADDR);
gcMap = (struct gcArray*)(GC_MAP_ADDR); int i;
for(i=PAGE_NUM_PER_BLOCK ; i> ; i--)      //从无效页大的开始回收
{
if(gcMap->gcEntry[dieNo][i].head != 0xffffffff)  //拥有这么多无效页的块存在的话,取出一块进行回收
{
u32 victimBlock = gcMap->gcEntry[dieNo][i].head; // GC victim block // link setting
if(blockMap->bmEntry[dieNo][victimBlock].nextBlock != 0xffffffff)  //更新GC链表
{
gcMap->gcEntry[dieNo][i].head = blockMap->bmEntry[dieNo][victimBlock].nextBlock;
blockMap->bmEntry[dieNo][blockMap->bmEntry[dieNo][victimBlock].nextBlock].prevBlock = 0xffffffff;
}
else
{
gcMap->gcEntry[dieNo][i].head = 0xffffffff;
gcMap->gcEntry[dieNo][i].tail = 0xffffffff;
} // copy valid pages from the victim block to the free block
if(i != PAGE_NUM_PER_BLOCK)    //如果整个块都是无效页就直接擦除就行了
{
int j;
for(j= ; j<PAGE_NUM_PER_BLOCK ; j++)  //
{
if(pageMap->pmEntry[dieNo][(victimBlock * PAGE_NUM_PER_BLOCK) + j].valid)
{
// page copy process
u32 validPage = victimBlock*PAGE_NUM_PER_BLOCK + j;
u32 freeBlock = dieBlock->dieEntry[dieNo].freeBlock;  //最开始有预留一个块
u32 freePage = freeBlock*PAGE_NUM_PER_BLOCK + blockMap->bmEntry[dieNo][freeBlock].currentPage; WaitWayFree(dieNo % CHANNEL_NUM, dieNo / CHANNEL_NUM);
SsdRead(dieNo % CHANNEL_NUM, dieNo / CHANNEL_NUM, validPage, GC_BUFFER_ADDR);    //将一个块里面的有效页读取到BUFFER里面
WaitWayFree(dieNo % CHANNEL_NUM, dieNo / CHANNEL_NUM);
SsdProgram(dieNo % CHANNEL_NUM, dieNo / CHANNEL_NUM, freePage, GC_BUFFER_ADDR);  //有效数据写入 // pageMap, blockMap update
u32 lpn = pageMap->pmEntry[dieNo][validPage].lpn; pageMap->pmEntry[dieNo][lpn].ppn = freePage;      //更新页映射信息
pageMap->pmEntry[dieNo][freePage].lpn = lpn;
blockMap->bmEntry[dieNo][freeBlock].currentPage++;
}
}
} // erased victim block becomes the free block for GC migration
EraseBlock(dieNo, victimBlock);
blockMap->bmEntry[dieNo][victimBlock].free = ; u32 currentBlock = dieBlock->dieEntry[dieNo].freeBlock;
dieBlock->dieEntry[dieNo].freeBlock = victimBlock;      //将刚擦出的块作为新的freeblock return currentBlock; // atomic GC completion
}
} // no free space anymore
assert(!"[WARNING] There are no free blocks. Abort terminate this ssd. [WARNING]");
return ;
}
上一篇:哈夫曼树(Huffman)的JS实现


下一篇:Python+Appium自动化测试(15)-使用Android模拟器(详细)