[發明專利]提高地址映射表中映射信息密度的方法

有效

• 申請號: 201710022698.0
• 申請日: 2017-01-12
• 公開（公告）號: CN107066393B
• 公開（公告）日: 2020-06-09
• 發明（設計）人: 樊進;彭春雨;高珊;李正平;譚守標;藺智挺;吳秀龍;陳軍寧;徐超;代月花
• 申請（專利權）人: 安徽大學
• 主分類號: G06F12/02
• 分類號: G06F12/02;G06F12/1027
• 代理公司: 北京凱特來知識產權代理有限公司 11260
• 代理人: 鄭立明;鄭哲

1.一種提高地址映射表中映射信息密度的方法，其特征在于，包括：

在寫入數據時，將數據按頁為單位進行分割，再按邏輯地址從低到高的順序將數據依次寫入存儲器中具有多個連續空閑頁的塊內，存儲后的每一頁數據均對應一條映射記錄，則根據這些映射記錄生成一到多條映射條目；如果寫入時沒有產生跨塊寫入，則映射記錄是連續的，能夠合并成1條映射條目；如果寫入時產生了跨塊寫入，則存儲在同一個塊內的數據對應的映射記錄是連續的，所對應的全部映射記錄能夠合并成1條映射條目；因此，如果寫入數據頁時產生了S次跨塊存儲，則共生成了S條映射條目；

在讀數據時，將讀請求地址按頁為單位進行分割，并逐一檢索內存中的緩存映射表，如果某一頁的邏輯地址沒有命中內存中的緩存映射表，則讀取存儲器中用于存儲映射表的映射表存儲頁，從映射表存儲頁中獲得所需的目標映射記錄；并且同時，還在該映射表存儲頁中檢索目標映射記錄周邊的映射記錄，將符合條件的周邊映射記錄通過合并生成一條映射條目，檢索過程如下：讀取映射表存儲頁內容，即映射表片段，再以目標映射記錄為起點向前后兩個方向檢索映射表片段，如果在某個方向中發現相鄰的映射記錄B與目標映射記錄的邏輯地址值與物理地址值都相差1，則以相鄰的映射記錄B為起點向同樣的方向繼續檢索映射表，直至兩個相鄰的映射記錄不再連續，或者雖然連續但已經存在于緩存映射表為止，或者檢索到映射表存儲頁中的第一條或最后一條映射記錄；

將寫入數據與讀數據時，所生成的映射條目插入所述內存中的緩存映射表。

2.根據權利要求1所述的一種提高地址映射表中映射信息密度的方法，其特征在于，在寫入數據時，如果寫入數據的頁數為N，存儲器中具有多個連續空閑頁的塊中的連續空閑頁數量為M，且NM時，則需要跨塊存儲，即需要剩余的數據頁按邏輯地址從低到高的順序將數據依次寫入其他具有多個連續空閑頁的塊內，直至所有數據頁均被寫入存儲器中；

如果寫入數據頁時產生了跨塊存儲，則每一映射條目中包含的映射記錄的數據即為相應塊中所存儲數據頁的數量。

3.根據權利要求1或2所述的一種提高地址映射表中映射信息密度的方法，其特征在于，所述映射條目存儲了若干個連續的映射記錄；如果一條邏輯地址LBA為L的映射記錄MPRec1，其物理地址PBA為P，如果另外一條邏輯地址LBA為L+1映射記錄MPRec2，其物理地址PBA為P+1，則映射記錄MPRec1和MPRec2是連續的，如果另外一條邏輯地址LBA為L+2映射記錄MPRec3，其物理地址PBA為P+2，則映射記錄MPRec1、MPRec2和MPRec3是連續的，以此類推，有N條映射記錄，其邏輯地址LBA的值從低到高是按照L、L+1、L+2、…、L+N-1連續增長的，相鄰映射記錄中記錄的邏輯地址的值相差1，而其物理地址PBA的值也是從低到高是按照P、P+1、P+2、…、P+N-1連續增長的，相鄰映射記錄中記錄的物理地址的值相差1，這樣的N條映射記錄即為連續的映射記錄。

4.根據權利要求3所述的一種提高地址映射表中映射信息密度的方法，其特征在于，映射條目由該連續的N條映射記錄中，具有最小邏輯地址那條映射記錄中的邏輯地址和物理地址以及一個長度值N和一個臟標志位組成；

其中映射條目的邏輯地址和物理地址所占的字節數，和相應映射記錄中的邏輯地址和物理地址所占的字節數相同，在使用另外用一個字節來存儲長度值N和臟標志位，臟標志位占用該字節的最高位，用來標識映射條目在緩存映射表的生存周期內是否被更改，如果發生了更改則賦值為1，否則值為0；條目的長度值保存在該字節的0到7位中。

5.根據權利要求1所述的一種提高地址映射表中映射信息密度的方法，其特征在于，將映射條目插入所述內存中的緩存映射表包括：

如果映射條目和緩存映射表中的既有條目產生因在邏輯地址上有交集而發生的沖突，則需要對相關映射條目進行分解并重新組合；

如果映射條目和緩存映射表中的既有條目是連續的，則需要對相關映射條目進行再次合并。

6.根據權利要求1所述的一種提高地址映射表中映射信息密度的方法，其特征在于，當映射條目插入所述內存中的緩存映射表后，如果接收到的讀請求命中映射條目，則直接計算出相應的物理地址，其步驟包括：

檢索緩存映射表，比對讀請求中的邏輯地址LBA和各映射條目所表示的邏輯地址范圍來判斷該LBA是否落在某條映射記錄所表示的邏輯地址范圍內；

對于某個長度為N的映射條目，其中存儲的邏輯地址為LBA1，物理地址為PBA1，當LBA＝LBA1，且LBA＝LBA1+N-1，則表示請求中的包含的邏輯地址命中了緩存映射表中的映射條目，讀請求中的邏輯地址LBA對應的物理地址PBA的計算方法為：PBA＝PBA1+LBA-LBA1，通過計算即可完成對物理地址的尋址。