[go: up one dir, main page]

TWI671631B - 記憶體管理方法以及儲存控制器 - Google Patents

記憶體管理方法以及儲存控制器 Download PDF

Info

Publication number
TWI671631B
TWI671631B TW107126694A TW107126694A TWI671631B TW I671631 B TWI671631 B TW I671631B TW 107126694 A TW107126694 A TW 107126694A TW 107126694 A TW107126694 A TW 107126694A TW I671631 B TWI671631 B TW I671631B
Authority
TW
Taiwan
Prior art keywords
block
block string
garbage collection
string
recycling
Prior art date
Application number
TW107126694A
Other languages
English (en)
Other versions
TW202008168A (zh
Inventor
蕭又華
謝宏志
Original Assignee
大陸商深圳大心電子科技有限公司
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 大陸商深圳大心電子科技有限公司 filed Critical 大陸商深圳大心電子科技有限公司
Priority to TW107126694A priority Critical patent/TWI671631B/zh
Priority to US16/137,539 priority patent/US10642731B2/en
Application granted granted Critical
Publication of TWI671631B publication Critical patent/TWI671631B/zh
Publication of TW202008168A publication Critical patent/TW202008168A/zh

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
    • G06F12/023—Free address space management
    • G06F12/0253—Garbage collection, i.e. reclamation of unreferenced memory
    • G06F12/0269—Incremental or concurrent garbage collection, e.g. in real-time systems
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
    • G06F12/023—Free address space management
    • G06F12/0238—Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
    • G06F3/0608—Saving storage space on storage systems
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0646—Horizontal data movement in storage systems, i.e. moving data in between storage devices or systems
    • G06F3/0652—Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0655—Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
    • G06F3/0659—Command handling arrangements, e.g. command buffers, queues, command scheduling
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
    • G06F3/0671—In-line storage system
    • G06F3/0673—Single storage device
    • G06F3/0679—Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/10—Providing a specific technical effect
    • G06F2212/1016—Performance improvement
    • G06F2212/1024—Latency reduction
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/10—Providing a specific technical effect
    • G06F2212/1041—Resource optimization
    • G06F2212/1044—Space efficiency improvement
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/72—Details relating to flash memory management
    • G06F2212/7205—Cleaning, compaction, garbage collection, erase control

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Human Computer Interaction (AREA)
  • Memory System (AREA)

Abstract

本發明提供一種記憶體管理方法。所述方法包括：執行垃圾回收指令；根據一或多個回收區塊串產生具有預定大小的垃圾回收資訊表，並且將所述垃圾回收資訊表寫入至目標區塊串，其中所述垃圾回收資訊表包括識別標籤、本地回收區塊串清單與第一填充資料；讀取所述一或多個回收區塊串的有效資料，並且將所述有效資料寫入至所述目標區塊串，其中所寫入的所述有效資料緊鄰於被寫入的所述垃圾回收資訊表後；以及關閉所述目標區塊串，並且將所述本地回收區塊串清單附加至緩衝記憶體中的一全域回收區塊串清單，以完成所述垃圾回收指令。

Description

記憶體管理方法以及儲存控制器
本發明是有關於一種記憶體管理方法，且特別是有關於一種適用於配置有可複寫式非揮發性記憶體模組的儲存裝置的記憶體管理方法與儲存控制器。
一般來說，配置有可複寫式非揮發性記憶體模組的儲存裝置的儲存控制器會執行垃圾回收操作來將多個來源實體區塊中的有效資料搬移至多個新實體區塊，並且抹除所述多個來源實體區塊，以釋放出所述多個來源實體區塊的無效資料所佔用的空間。
傳統上，在多個實體區塊執行垃圾回收操作的過程中，在所述多個實體區塊有任何的資訊變動時，會以快照（Snapshot）操作來保存原本維護於緩衝記憶體中的對應所執行的垃圾回收操作的所述多個實體區塊的資訊至可複寫式非揮發性記憶體模組。如此一來，在執行垃圾回收操作的期間，會因為頻繁地執行快照操作，而耗費了大量時間，進而導致了儲存裝置的大量延遲。
因此，如何較有效率地保存所述垃圾回收操作的資訊，以降低因為執行垃圾回收操作所導致的延遲，進而增進儲存裝置的工作效率，是本領域人員研究的課題之一。
本發明提供一種記憶體管理方法，可在開始執行垃圾回收操作時，根據被執行所述垃圾回收操作的回收區塊串的資訊產生垃圾回收資訊表且將所述垃圾回收資訊表寫入至對應所述垃圾回收操作的目標區塊串。此外，所述記憶體管理方法亦可在斷電事件發生時，執行恢復操作，以利用儲存在目標區塊串的垃圾資訊表來重建全域回收區塊串清單。
本發明的一實施例提供一種記憶體管理方法，適用於配置有可複寫式非揮發性記憶體模組的儲存裝置，其中所述可複寫式非揮發性記憶體模組具有多個實體區塊，所述多個實體區塊被分組為多個區塊串。所述方法包括：一種記憶體管理方法，適用於配置有一可複寫式非揮發性記憶體模組的一儲存裝置，其中所述可複寫式非揮發性記憶體模組具有多個實體區塊，並且所述多個實體區塊被分組為多個區塊串，所述方法包括：執行垃圾回收指令，其中所述垃圾回收指令指示將一或多個回收區塊串的有效資料收集至目標區塊串；根據所述一或多個回收區塊串產生具有預定大小的垃圾回收資訊表，並且將所述垃圾回收資訊表寫入至所述目標區塊串，其中所述垃圾回收資訊表包括識別標籤、本地回收區塊串清單與第一填充資料；讀取所述一或多個回收區塊串的有效資料，並且將所述有效資料寫入至所述目標區塊串，其中所寫入的所述有效資料緊鄰於被寫入的所述垃圾回收資訊表後；以及關閉所述目標區塊串，並且將所述本地回收區塊串清單附加至一緩衝記憶體中的一全域回收區塊串清單，以完成所述垃圾回收指令。
本發明的一實施例提供用於控制配置有可複寫式非揮發性記憶體模組的儲存裝置的一種儲存控制器。所述儲存控制器包括：連接介面電路、記憶體介面控制電路、垃圾回收管理電路單元以及處理器。連接介面電路用以耦接至主機系統。記憶體介面控制電路用以耦接至所述可複寫式非揮發性記憶體模組，其中所述可複寫式非揮發性記憶體模組具有多個實體區塊，所述多個實體區塊被分組為多個區塊串。所述處理器耦接至所述連接介面電路、所述記憶體介面控制電路與所述垃圾回收管理電路單元。所述垃圾回收管理電路單元用以執行從所述處理器所接收的垃圾回收指令，其中所述垃圾回收指令指示將一或多個回收區塊串的有效資料收集至目標區塊串，其中所述垃圾回收管理電路單元更用以根據所述一或多個回收區塊串產生具有預定大小的垃圾回收資訊表，並且指示所述記憶體介面控制電路將所述垃圾回收資訊表寫入至所述目標區塊串。所述垃圾回收資訊表包括識別標籤、本地回收區塊串清單與第一填充資料。所述垃圾回收管理電路單元更用以讀取所述一或多個回收區塊串的有效資料，並且將所述有效資料寫入至所述目標區塊串，其中所寫入的所述有效資料緊鄰於被寫入的所述垃圾回收資訊表後。所述垃圾回收管理電路單元更用以關閉所述目標區塊串，並且將所述本地回收區塊串清單附加至緩衝記憶體中的全域回收區塊串清單，以完成所述垃圾回收指令。
基於上述，本發明實施例所提供的記憶體管理方法以及儲存控制器，可僅在反應於開始執行一垃圾回收操作時，根據被執行所述垃圾回收操作的回收區塊串產生垃圾回收資訊表，將所述垃圾回收資訊表寫入至對應所述垃圾回收操作的目標區塊串，再將回收區塊串的有效資料複製至已具有垃圾回收資訊表的所述目標區塊串中，以完成所述垃圾回收操作。此外，在每個目標區塊串中的垃圾回收資訊表也可被用於重建全域回收區塊串清單，以輔助管理儲存裝置整體的區塊串的使用狀況。如此一來，可在減少垃圾回收操作所導致的存取延遲的情況下，依然可以讓儲存裝置所儲存的資料具有可靠性，進而提昇了儲存裝置的工作效率。
為讓本發明的上述特徵和優點能更明顯易懂，下文特舉實施例，並配合所附圖式作詳細說明如下。
在本實施例中，儲存裝置包括可複寫式非揮發性記憶體模組(rewritable non-volatile memory module)與儲存裝置控制器(亦稱，儲存控制器或儲存控制電路)。此外，儲存裝置是與主機系統一起使用，以使主機系統可將資料寫入至儲存裝置或從儲存裝置中讀取資料。
圖1是根據本發明的一實施例所繪示的主機系統及儲存裝置的方塊示意圖。
請參照圖1，主機系統(Host System)10包括處理器(Processor)110、主機記憶體(Host Memory)120及資料傳輸介面電路(Data Transfer Interface Circuit)130。在本實施例中，資料傳輸介面電路130耦接(亦稱，電性連接)至處理器110與主機記憶體120。在另一實施例中，處理器110、主機記憶體120與資料傳輸介面電路130之間利用系統匯流排(System Bus)彼此耦接。
儲存裝置20包括儲存控制器(Storage Controller)210、可複寫式非揮發性記憶體模組(Rewritable Non-Volatile Memory Module)220及連接介面電路(Connection Interface Circuit)230。其中，儲存控制器210包括處理器211、資料管理電路(Data Management Circuit)212與記憶體介面控制電路(Memory Interface Control Circuit)213。
在本實施例中，主機系統10是透過資料傳輸介面電路130與儲存裝置20的連接介面電路230耦接至儲存裝置20來進行資料的存取操作。例如，主機系統10可經由資料傳輸介面電路130將資料儲存至儲存裝置20或從儲存裝置20中讀取資料。
在本實施例中，處理器110、主機記憶體120及資料傳輸介面電路130可設置在主機系統10的主機板上。資料傳輸介面電路130的數目可以是一或多個。透過資料傳輸介面電路130，主機板可以經由有線或無線方式耦接至儲存裝置20。儲存裝置20可例如是隨身碟、記憶卡、固態硬碟(Solid State Drive，SSD)或無線記憶體儲存裝置。無線記憶體儲存裝置可例如是近距離無線通訊(Near Field Communication，NFC)記憶體儲存裝置、無線傳真(WiFi)記憶體儲存裝置、藍牙(Bluetooth)記憶體儲存裝置或低功耗藍牙記憶體儲存裝置(例如，iBeacon)等以各式無線通訊技術為基礎的記憶體儲存裝置。此外，主機板也可以透過系統匯流排耦接至全球定位系統(Global Positioning System，GPS)模組、網路介面卡、無線傳輸裝置、鍵盤、螢幕、喇叭等各式I/O裝置。
在本實施例中，資料傳輸介面電路130與連接介面電路230是相容於高速周邊零件連接介面(Peripheral Component Interconnect Express, PCI Express)標準的介面電路。並且，資料傳輸介面電路130與連接介面電路230之間是利用快速非揮發性記憶體介面標準(Non-Volatile Memory express，NVMe)通訊協定來進行資料的傳輸。
然而，必須瞭解的是，本發明不限於此，資料傳輸介面電路130與連接介面電路230亦可以是符合並列先進附件(Parallel Advanced Technology Attachment，PATA)標準、電氣和電子工程師協會(Institute of Electrical and Electronic Engineers，IEEE)1394標準、序列先進附件(Serial Advanced Technology Attachment，SATA)標準、通用序列匯流排(Universal Serial Bus，USB)標準、SD介面標準、超高速一代(Ultra High Speed-I，UHS-I)介面標準、超高速二代(Ultra High Speed-II，UHS-II)介面標準、記憶棒(Memory Stick, MS)介面標準、多晶片封裝(Multi-Chip Package)介面標準、多媒體儲存卡(Multi Media Card，MMC)介面標準、eMMC介面標準、通用快閃記憶體(Universal Flash Storage，UFS)介面標準、eMCP介面標準、CF介面標準、整合式驅動電子介面(Integrated Device Electronics，IDE)標準或其他適合的標準。此外，在另一實施例中，連接介面電路230可與儲存控制器210封裝在一個晶片中，或者連接介面電路230是佈設於一包含儲存控制器210之晶片外。
在本實施例中，主機記憶體120用以暫存處理器110所執行的指令或資料。例如，在本範例實施例中，主機記憶體120可以是動態隨機存取記憶體（Dynamic Random Access Memory，DRAM）、靜態隨機存取記憶體(Static Random Access Memory，SRAM)等。然而，必須瞭解的是，本發明不限於此，主機記憶體120也可以是其他適合的記憶體。
儲存控制器210用以執行以硬體型式或韌體型式實作的多個邏輯閘或控制指令並且根據主機系統10的指令在可複寫式非揮發性記憶體模組220中進行資料的寫入、讀取與抹除等運作。
更詳細來說，儲存控制器210中的處理器211為具備運算能力的硬體，其用以控制儲存控制器210的整體運作。具體來說，處理器211具有多個控制指令，並且在儲存裝置20運作時，此些控制指令會被執行以進行資料的寫入、讀取與抹除等運作。
值得一提的是，在本實施例中，處理器110與處理器211例如是中央處理單元(Central Processing Unit，CPU)、微處理器(micro-processor)、或是其他可程式化之處理單元(Microprocessor)、數位訊號處理器(Digital Signal Processor，DSP)、可程式化控制器、特殊應用積體電路(Application Specific Integrated Circuits，ASIC)、可程式化邏輯裝置(Programmable Logic Device，PLD)或其他類似電路元件，本發明並不限於此。
在一實施例中，儲存控制器210還具有唯讀記憶體(未繪示)及隨機存取記憶體(未繪示)。特別是，此唯讀記憶體具有開機碼(boot code)，並且當儲存控制器210被致能時，處理器211會先執行此開機碼來將儲存於可複寫式非揮發性記憶體模組220中之控制指令載入至儲存控制器210的隨機存取記憶體中。之後，處理器211會運轉此些控制指令以進行資料的寫入、讀取與抹除等運作。在另一實施例中，處理器211的控制指令亦可以程式碼型式儲存於可複寫式非揮發性記憶體模組220的特定區域，例如，可複寫式非揮發性記憶體模組220中專用於存放系統資料的實體儲存單元中。
在本實施例中，如上所述，儲存控制器210還包括資料管理電路212與記憶體介面控制電路213。應注意的是，儲存控制器220各部件所執行的操作亦可視為儲存控制器220所執行的操作。
其中，資料管理電路212耦接至處理器211、記憶體介面控制電路213與連接介面電路230。資料管理電路212用以接受處理器211的指示來進行資料的傳輸。例如，經由連接介面電路230從主機系統10(如，主機記憶體120)讀取資料，並且將所讀取的資料經由記憶體介面控制電路213寫入至可複寫式非揮發性記憶體模組220中（如，根據來自主機系統10的寫入指令來進行寫入操作）。又例如，經由記憶體介面控制電路213從可複寫式非揮發性記憶體模組220的一或多個實體單元中讀取資料(資料可讀取自一或多個實體單元中的一或多個記憶胞)，並且將所讀取的資料經由連接介面電路230寫入至主機系統10(如，主機記憶體120)中（如，根據來自主機系統10的讀取指令來進行讀取操作）。在另一實施例中，資料管理電路212亦可整合至處理器211中。
記憶體介面控制電路213用以接受處理器211的指示，配合資料管理電路212來進行對於可複寫式非揮發性記憶體模組220的寫入(亦稱，程式化，Programming)操作、讀取操作或抹除操作。
舉例來說，處理器211可執行寫入指令序列，以指示記憶體介面控制電路213將資料寫入至可複寫式非揮發性記憶體模組220中；處理器211可執行讀取指令序列，以指示記憶體介面控制電路213從可複寫式非揮發性記憶體模組220的對應讀取指令的一或多個實體單元（亦稱，目標實體單元）中讀取資料；處理器211可執行抹除指令序列，以指示記憶體介面控制電路213對可複寫式非揮發性記憶體模組220進行抹除操作。寫入指令序列、讀取指令序列及抹除指令序列可各別包括一或多個程式碼或指令碼並且用以指示對可複寫式非揮發性記憶體模組220執行相對應的寫入、讀取及抹除等操作。在一實施例中，處理器211還可以下達其他類型的指令序列給記憶體介面控制電路213，以對可複寫式非揮發性記憶體模組220執行相對應的操作。
此外，欲寫入至可複寫式非揮發性記憶體模組220的資料會經由記憶體介面控制電路213轉換為可複寫式非揮發性記憶體模組220所能接受的格式。具體來說，若處理器211要存取可複寫式非揮發性記憶體模組220，處理器211會傳送對應的指令序列給記憶體介面控制電路213以指示記憶體介面控制電路213執行對應的操作。例如，這些指令序列可包括指示寫入資料的寫入指令序列、指示讀取資料的讀取指令序列、指示抹除資料的抹除指令序列、以及用以指示各種記憶體操作(例如，改變預設讀取電壓組的多個預設讀取電壓值以進行讀取操作，或執行垃圾回收程序等等)的相對應的指令序列。這些指令序列可包括一或多個訊號，或是在匯流排上的資料。這些訊號或資料可包括指令碼或程式碼。例如，在讀取指令序列中，會包括讀取的辨識碼、記憶體位址等資訊。
可複寫式非揮發性記憶體模組220是耦接至儲存控制器210（記憶體介面控制電路213）並且用以儲存主機系統10所寫入之資料。可複寫式非揮發性記憶體模組220可以是單階記憶胞(Single Level Cell，SLC)NAND型快閃記憶體模組(即，一個記憶胞中可儲存1個位元的快閃記憶體模組)、多階記憶胞(Multi Level Cell，MLC)NAND型快閃記憶體模組(即，一個記憶胞中可儲存2個位元的快閃記憶體模組)、三階記憶胞(Triple Level Cell，TLC)NAND型快閃記憶體模組(即，一個記憶胞中可儲存3個位元的快閃記憶體模組)、四階記憶胞(Quadruple Level Cell，QLC)NAND型快閃記憶體模組(即，一個記憶胞中可儲存4個位元的快閃記憶體模組)、三維NAND型快閃記憶體模組（3D NAND flash memory module）或垂直NAND型快閃記憶體模組（Vertical NAND flash memory module）等其他快閃記憶體模組或其他具有相同特性的記憶體模組。可複寫式非揮發性記憶體模組220中的記憶胞是以陣列的方式設置。
在本實施例中，可複寫式非揮發性記憶體模組220具有多個字元線，其中所述多個字元線的每一個字元線包括多個記憶胞。同一條字元線上的多個記憶胞會組成一或多個實體程式化單元（實體頁面）。此外，多個實體程式化單元可組成一個實體單元（實體區塊或實體抹除單元）。
在本實施例中，是以一個實體頁面作為寫入(程式化)資料的最小單位。實體單元（實體區塊）為抹除之最小單位，即，每一實體單元含有最小數目之一併被抹除之記憶胞。此外，每個實體頁面的位址亦可稱為實體位址。
應注意的是，在本實施例中，用以記錄一實體區塊或區塊串的資訊的系統資料可利用該實體區塊中的一或多個記憶胞來記錄，或是利用一個系統區中用以記錄所有系統資料的特定實體區塊（亦稱，系統實體區塊）的一或多個記憶胞來記錄。
此外，必須瞭解的是，當處理器211對可複寫式非揮發性記憶體模組220中的記憶胞(或實體單元)進行分組以執行對應的管理操作時，此些記憶胞(或實體單元)是被邏輯地分組，而其實際位置並未更動。
儲存控制器210會配置多個邏輯單元給可複寫式非揮發性記憶體模組220。主機系統10是透過所配置的邏輯單元來存取儲存在多個實體單元中的使用者資料。在此，每一個邏輯單元可以是由一或多個邏輯位址組成。例如，邏輯單元可以是邏輯區塊(Logical Block)、邏輯頁面(Logical Page)或是邏輯扇區(Logical Sector)。一個邏輯單元可以是映射至一或多個實體單元，其中實體單元可以是一或多個實體位址、一或多個實體扇、一或多個實體程式化單元或者一或多個實體抹除單元。在本實施例中，邏輯單元為邏輯區塊，並且邏輯子單元為邏輯頁面。每一邏輯單元具有多個邏輯子單元。在本實施例中，邏輯子單元的位址亦稱為邏輯位址。
此外，儲存控制器210會建立邏輯轉實體位址映射表(Logical To Physical address mapping table)與實體轉邏輯位址映射表(Physical To Logical address mapping table)，以記錄配置給可複寫式非揮發性記憶體模組220的邏輯位址與實體位址之間的映射關係。換言之，儲存控制器210可藉由邏輯轉實體位址映射表來查找一邏輯位址所映射的實體位址，並且儲存控制器210可藉由實體轉邏輯位址映射表來查找一實體位址所映射的邏輯位址。然而，上述有關邏輯位址與實體位址之間的映射關係的技術概念為本領域技術人員之慣用技術手段，不再贅述於此。在儲存控制器的一般運作中，所述邏輯轉實體位址映射表與實體轉邏輯位址映射表可被維護於緩衝記憶體216中。
在本實施例中，錯誤檢查與校正電路214是耦接至處理器211並且用以執行錯誤檢查與校正程序以確保資料的正確性。具體來說，當處理器211從主機系統10中接收到寫入指令時，錯誤檢查與校正電路214會為對應此寫入指令的資料產生對應的錯誤更正碼(error correcting code，ECC)及/或錯誤檢查碼(error detecting code，EDC)，並且處理器211會將對應此寫入指令的資料與對應的錯誤更正碼及/或錯誤檢查碼寫入至可複寫式非揮發性記憶體模組220中。之後，當處理器211從可複寫式非揮發性記憶體模組220中讀取資料時會同時讀取此資料對應的錯誤更正碼及/或錯誤檢查碼，並且錯誤檢查與校正電路214會依據此錯誤更正碼及/或錯誤檢查碼對所讀取的資料執行錯誤檢查與校正程序。
在一實施例中，儲存控制器210還包括緩衝記憶體216與電源管理電路217。緩衝記憶體216是耦接至處理器211並且用以暫存來自於主機系統10的資料與指令、來自於可複寫式非揮發性記憶體模組220的資料或其他用以管理儲存裝置20的系統資料，以讓處理器211可快速地從緩衝記憶體216中存取所述資料、指令或系統資料。電源管理電路217是耦接至處理器211並且用以控制儲存裝置20的電源。
在本實施例中，垃圾回收管理電路單元215包括垃圾回收執行電路2151與回收區塊串記錄電路2152。所述垃圾回收管理電路單元215用以接收處理器211指示來執行寫入指令或重新程式化操作。應注意的是，在一實施例中，上述垃圾回收管理電路單元215亦可整合至處理器211中，以使處理器211可實行本實施例所提供的資料寫入方法。另外，在另一實施例中，垃圾回收管理電路單元215亦可以韌體或軟體的方式被實做為垃圾回收管理程式碼模組，被處理器211所存取且執行，以實現本發明所提供的記憶體管理方法。
應注意的是，在本實施例中，所述垃圾回收操作是針對一個區塊串來執行的。以下會藉由圖3來說明區塊串的細節。
圖3為根據本發明的一實施例所繪示可複寫式非揮發性記憶體模組的多個區塊串的示意圖。請參照圖3，在本實施例中，可複寫式非揮發性記憶體模組220可具有多個封裝（Pakage），每個封裝可具有多個實體區塊，所述多個實體區塊可被劃分至N個平面，並且部份或全部的平面可邏輯地劃分為一個邏輯數(Logical unit number，LUN)。為了簡便說明，假設可複寫式非揮發性記憶體模組220具有一個封裝D1，並且封裝D1具有多個實體區塊。所述多個實體區塊被劃分（被分組）為4個平面（Plane）P1~P4中（N等於4），其中所述4個平面被劃分為一個邏輯數LUN1。此外，每個平面具有依據第一順序排列的M個實體單元，如，平面P1具有M個實體區塊P1(1)~P1(M)；平面P2具有M個實體區塊P2(1)~P2(M)；平面P3具有M個實體區塊P3(1)~P3(M)；平面P4具有M個實體區塊P4(1)~P4(M)。在本實施例中，每個平面中排列順序相同的實體區塊會被組成一個區塊串（Block Stripe）。例如，區塊串BS(1)包括實體區塊P1(1)、實體區塊P2(1)、實體區塊P3(1)與實體區塊P4(1)。也就是說，上述4個平面中的所有實體區塊可組成依據第一順序排列的M個區塊串BS(1)~BS(M)。
在本實施例中，儲存控制器210是依據區塊串的順序來循序寫入資料至多個區塊串中，並且在同一個區塊串中，會依據平面P1~P4的順序來寫入資料。假設所有區塊串皆為空白，為了寫入一筆可填滿4個實體區塊的寫入資料，儲存控制器210會依據第一順序從第一個空白的區塊串(在此例子為區塊串BS(1))，來將所述寫入資料儲存至所述第一個空白的區塊串的所有實體區塊中（如，實體區塊P1(1)、實體區塊P2(1)、實體區塊P3(1)與實體區塊P4(1)中）。又例如，假設區塊串BS(1)的實體區塊P1(1)不可用來儲存所述資料，並且其他實體區塊皆可用來儲存所述寫入資料，則儲存控制器210會將所述寫入資料儲存至區塊串BS(1)的實體區塊P2(1)、實體區塊P3(1)與實體區塊P4(1)以及區塊串BS(2)的實體區塊P1(2)中。
在本實施例中，垃圾回收管理電路單元215(或垃圾回收執行電路2151)用以接收處理器211的指示來對一或多個區塊串執行垃圾回收操作。垃圾回收管理電路單元215(或回收區塊串記錄電路2152)用以記錄相應於被執行所述垃圾回收操作的所述一或多個區塊串的資訊。以下會配合多個圖式來詳細說明本發明之實施例所提供的資料寫入方法的細節，以及對應所述資料寫入方法的儲存控制器210與垃圾回收管理電路單元215的功能。
圖2A是根據本發明的一實施例所繪示的記憶體管理方法的流程圖。請同時參照圖1與圖2A，在步驟S211中，垃圾回收管理電路單元215執行垃圾回收指令，其中所述垃圾回收指令指示將一或多個回收區塊串的有效資料收集至目標區塊串。
具體來說，處理器211可記錄可複寫式非揮發性記憶體模組220的多個區塊串的有效資料計數值。當一個空的區塊串剛被寫滿資料時，此區塊串的有效資料計數值為最大。當一區塊串的所述有效資料計數值降低至低於一有效資料門檻值（或當一區塊串的所述無效資料計高於一無效資料門檻值）時，處理器211會將此區塊串的區塊串索引值記錄起來，以準備對此區塊串（亦可稱為，來源區塊串）執行垃圾回收操作。在特定時機時，處理器211可發送垃圾回收指令給垃圾回收管理電路單元215，以指示垃圾回收管理電路單元215開始對上述的來源區塊串（亦稱，回收區塊串）執行垃圾回收操作，以將此回收區塊串中的有效資料收集（複製）至一可用區塊串（亦稱，目標區塊串）。
換句話說，在所述垃圾回收指令中至少會包括兩種資訊，一種是被收集有效資料的回收區塊串的資訊，另一種是目標區塊串。垃圾回收管理電路單元215可藉由所述垃圾回收指令辨識所述垃圾回收指令所指示的所述一或多個回收區塊串的區塊串索引值（亦稱，回收區塊串索引值）以及目標區塊串的區塊串索引值（亦稱，目標區塊串索引值）。一個區塊串的區塊串索引值（如，上述的BS(1)）可用以讓儲存控制器210的各元件來識別所述區塊串及所述區塊串中的多個實體區塊。此外，所述區塊串索引值亦可用以表示對應的區塊串於可複寫式非揮發性記憶體模組220中的位置。
值得一提的是，處理器211可再利用所述回收區塊串。具體來說，處理器211可在適當的時機（如，儲存裝置閒暇時）對所述回收區塊串執行抹除操作，以使所述回收區塊串中的實體區塊成為空白實體區塊，進而可被寫入資料。此外，在一實施例中，處理器211亦可先選擇回收區塊串來執行寫入操作，並且在寫入對應寫入操作的資料之前，先對回收區塊串來執行抹除操作。
接著，在步驟S212中，垃圾回收管理電路單元215(或回收區塊串記錄電路2152)根據所述一或多個回收區塊串產生具有預定大小的垃圾回收資訊表，並且將所述垃圾回收資訊表寫入至所述目標區塊串，其中所述垃圾回收資訊表包括識別標籤、本地回收區塊串清單與第一填充資料。以下利用圖4A來說明所產生的垃圾回收資訊表的架構。
圖4A為根據本發明的一實施例所繪示垃圾回收資訊表的資料結構的示意圖。請參照圖4A，在本實施例中，所述垃圾回收資訊表400主要包括本地回收區塊串清單。所述本地回收區塊串清單用以記錄對應所述垃圾回收指令的一或多個回收區塊串的一或多個回收區塊串索引值RBI[1]~RBI[Y]。Y為正整數。
此外，在本實施例中，為了資料管理的方便，所產生的垃圾回收資訊表的大小是一預定大小。所述預定大小例如是一個實體頁面的大小或一個碼字（Codeword）的大小，本發明不限於此。垃圾回收管理電路單元215(或回收區塊串記錄電路2152)會分別附加資料標籤DT以及填充資料PD1（亦稱，第一填充資料）至本地回收區塊串清單的前後，以形成垃圾回收資訊表400。
所述資料標籤DT被附加至垃圾回收資訊表400的最前方，並且資料標籤DT用以表示資料標籤DT與位於資料標籤DT後的多種資料為具有預定大小的垃圾回收資訊表。所述資料標籤DT所佔用的空間大小可被預先設定。所述多種資料包括本地回收區塊串清單與第一填充資料。
所述第一填充資料PD1被用以使垃圾回收資訊表400的大小為預定大小。具體來說，垃圾回收管理電路單元215(或回收區塊串記錄電路2152)會計算當前更新後的垃圾回收資訊表400中的資料標籤DT與回收區塊串清單所共同佔用的總空間的大小，並且將所述預定大小減去所述總空間大小所獲得的差值作為所述第一填充資料PD1的大小。如此一來，在附加第一填充資料PD1至垃圾回收資訊表400後，可使垃圾回收資訊表400的總大小為所述預定大小。此時，產生垃圾回收資訊表400的運作就完成了。應注意的是，所述資料標籤DT與所述每一個回收區塊串索引值RBI[1]~RBI[Y]所佔用的空間大小可被預先設定。
圖4B為根據本發明的一實施例所繪示的寫入垃圾回收資訊表至目標區塊串的示意圖。在產生垃圾回收資訊表後，垃圾回收管理電路單元215(或回收區塊串記錄電路2152)指示記憶體介面控制電路213將所產生的垃圾回收資訊表寫入至所述目標區塊串。
舉例來說，請參照圖4B，假設在空白的目標區塊串BS(M)中具有對應四個平面的實體區塊P1(M)～P4(M)，並且每個實體區塊具有N個實體頁面Page[1]~Page[N]。垃圾回收管理電路單元215(或回收區塊串記錄電路2152)會指示記憶體介面控制電路213將所產生的垃圾回收資訊表400寫入至目標區塊串BS(M)的第一個實體區塊P1(M)的第一個實體頁面Page[1]的最前方。
在寫入垃圾回收資訊表後，會開始寫入所述一或多個回收區塊串的有效資料至目標區塊串。即，在步驟S213中，垃圾回收管理電路單元215(或垃圾回收執行電路2151) 指示記憶體介面控制電路213讀取所述一或多個回收區塊串的所述有效資料，並且指示記憶體介面控制電路213將所述有效資料寫入至所述目標區塊串，其中所寫入的所述有效資料緊鄰於被寫入的所述垃圾回收資訊表後。
也就是說，接續上方圖4B的例子，在寫入垃圾回收資訊表400後，所述一或多個回收區塊串中的有效資料會依序被寫入至所述目標區塊串BS(M)且排列在所寫入的垃圾回收資訊表400後。例如，所述有效資料會先被寫入至實體區塊P1(M)的第一個實體頁面Page[1]且排列在所寫入的垃圾回收資訊表400後，接著被寫入至實體區塊P1(M)的其他實體頁面Page[2]~Page[N]，接著被寫入至實體區塊P2(M)、實體區塊P3(M)與實體區塊P4(M)。
在寫入所有的所述一或多個回收區塊串中的所述有效資料後，接著，在步驟S214中，垃圾回收管理電路單元215(或垃圾回收執行電路2151)判斷所述目標區塊串是否具有剩餘空間。
反應於所述目標區塊串具有剩餘空間，接續至步驟S215，垃圾回收管理電路單元215(或垃圾回收執行電路2151)指示記憶體介面控制電路213寫滿第二填充資料至所述剩餘空間。
舉例來說，接續圖4B的例子，假設在寫完所有有效資料後，實體區塊P4(M)的最後一個實體頁面Page[N]還有空間可以寫入資料（所述目標區塊串具有剩餘空間）。此時，垃圾回收管理電路單元215(或垃圾回收執行電路2151)指示記憶體介面控制電路213寫入第二填充資料PD2至實體區塊P4(M)的最後一個實體頁面Page[N]。接著，接續至步驟S216，垃圾回收管理電路單元215(或垃圾回收執行電路2151)指示記憶體介面控制電路213關閉所述目標區塊串，並且垃圾回收管理電路單元215(或回收區塊串記錄電路2152)將所述本地回收區塊串清單附加至緩衝記憶體216中的全域回收區塊串清單，以完成所述垃圾回收指令。應注意的是，用以儲存所述有效資料的多個邏輯位址與多個實體位址的映射關係也會一併被更新。
具體來說，在寫入第二填充資料PD2後，所述目標區塊串已經不存在任何可用空間，並且所述目標區塊串的所有實體區塊P1(M)~P4(M)會被關閉，即，被設定不能再被寫入任何資料。接著，垃圾回收管理電路單元215(或回收區塊串記錄電路2152)會將對應所述一或多個回收區塊串的本地回收區塊串清單附加至緩衝記憶體216中的全域回收區塊串清單，以讓處理器211可利用緩衝記憶體216中的全域回收區塊串清單來辨識目前可複寫式非揮發性記憶體模組220的所有回收區塊串。
圖4C為根據本發明的一實施例所繪示的全域回收區塊串清單的資料結構的示意圖。請參照圖4C，全域回收區塊串清單410的結構相似於垃圾回收資訊表400的本地回收區塊串清單。即，所述全域回收區塊串清單410用以記錄所有回收區塊串的回收區塊串索引值RBI[1]~RBI[X]。X為正整數且大於Y。也就是說，在對應所述一或多個回收區塊串的本地回收區塊串清單被附加至緩衝記憶體216中的全域回收區塊串清單410後，全域回收區塊串清單410所記錄的回收區塊串索引值RBI[1]~RBI[X]會包含本地回收區塊串清單所記錄的回收區塊串索引值RBI[1]~RBI[Y]。
在將對應所述一或多個回收區塊串的本地回收區塊串清單附加至緩衝記憶體216中的全域回收區塊串清單410後，垃圾回收管理電路單元215(或回收區塊串記錄電路2152)會判定所述垃圾回收指令完成。如上述，此時，處理器211可相應地更新用以儲存所述有效資料的多個邏輯位址與多個實體位址的映射關係。
請再回到圖2A，另一方面，在執行步驟S214後，反應於所述目標區塊串不具有剩餘空間，回收管理電路單元215(或回收區塊串記錄電路2152)判定不需要寫入第二填充資料，並且接續執行步驟S216。
應理解的是，本發明並不限定上述第一、第二填充資料PD1、PD2的位元值的設定方式。例如，上述第一、第二填充資料PD1、PD2可利用亂數函數產生。或是上述第一、第二填充資料PD1、PD2可利用固定態樣的資料來產生。
在本實施例中，除了反應所執行的垃圾回收操作來更新全域回收區塊串清單之外，還可根據區塊串的使用來判斷是否更新全域回收區塊串清單。
圖2B是根據本發明的一實施例所繪示的記憶體管理方法的流程圖。請參照圖2B，在步驟S221中，處理器211使用標的區塊串。具體來說，當處理器211欲執行寫入操作或資料合併操作以寫入一筆資料時，處理器211會從可複寫式非揮發性記憶體模組220中的多個可用區塊串（Available Block Stripe）中選擇其中一個或多個可用區塊串（亦稱，標的區塊串，Subject Block Stripe）來寫入該筆資料。被選擇以寫入資料的標的區塊串亦可視為被使用的標的區塊串。所述可用區塊串包括已經完成垃圾回收操作的回收區塊串（Recycled Block Stripe）、自由區塊串（Free Block Stripe）或空白區塊串（Empty Blcok Stripe）。在本實施例中，處理器211會根據標的區塊串被選擇以使用的時間點來記錄對應標的區塊串的時間戳記（亦稱，區塊串時間戳記）至系統實體區塊。或是，在另一實施例中，標的區塊串本身會具有閒置區域（Spare area）以存放對應標的區塊串的元資料（Meta data），並且所述元資料可記錄標的區塊串的區塊串時間戳記。
接著，在步驟S222中，垃圾回收管理電路單元215(或回收區塊串記錄電路2152) 對照所述標的區塊串的標的區塊串索引值與全域回收區塊串清單所記錄的多個回收區塊串索引值。具體來說，垃圾回收管理電路單元215(或回收區塊串記錄電路2152)會辨識被使用的標的區塊串的區塊串索引值（亦稱，標的區塊串索引值），並且根據所述標的區塊串索引值來對照全域回收區塊串清單中所有的回收區塊串索引值，以查找是否有相符/相等於標的區塊串索引值的回收區塊串索引值。
接著，在步驟S223中，反應於所述標的區塊串索引值相符於所述多個回收區塊串索引值中的一標的回收區塊串索引值，垃圾回收管理電路單元215(或回收區塊串記錄電路2152) 從所述全域回收區塊串清單所記錄的所述多個回收區塊串索引值中刪除所述標的回收區塊串索引值。如此一來，便完成了因標的區塊串的使用所執行的全域回收區塊串清單的更新操作。當全域回收區塊串清單的標的回收區塊串索引值被刪除時，排列在被刪除的標的回收區塊串索引值後的所有回收區塊串索引值會往前排列。例如，當標的回收區塊串索引值RBI[1]被刪除時，標的回收區塊串索引值RBI[1]後面的回收區塊串索引值RBI[2]～RBI[X]會往前遞補，即，全域回收區塊串清單會從回收區塊串索引值RBI[2]開始排列至回收區塊串索引值RBI[X]。應注意的是，所述每一個回收區塊串索引值所佔用的空間大小可被預先設定。
應注意的是，在完成此態樣的更新操作後，並不會對目前維護在緩衝記憶體216的全域回收區塊串清單執行快照操作，即，緩衝記憶體216的全域回收區塊串清單並不會被寫入至可複寫式非揮發性記憶體模組220。
由於全域回收區塊串清單僅儲存在緩衝記憶體216中。因此，若儲存裝置突然發生斷電（亦稱，突然斷電事件），緩衝記憶體216所儲存的全域回收區塊串清單及其他資料都會丟失。基此，垃圾回收管理電路單元215可因應突然斷電事件來執行恢復操作，以嘗試復原在突然斷電之前的緩衝記憶體216中的全域回收區塊串清單。
圖5是根據本發明的一實施例所繪示的恢復操作的流程圖。請參照圖5，在步驟S51中，回收管理電路單元215(或回收區塊串記錄電路2152) 辨識可複寫式非揮發性記憶體模組的所有目標區塊串中的多個已關閉目標區塊串。具體來說，回收管理電路單元215(或回收區塊串記錄電路2152)可利用資料標籤DT來從可複寫式非揮發性記憶體220的所有區塊串中辨識多個目標區塊串。即，前方儲存有垃圾回收資訊表的區塊串會被辨識為目標區塊串。此外，相應於上述的步驟S216，已經被關閉的目標區塊串才可以被視為完成垃圾回收操作。
反之，當執行垃圾回收操作的目標區塊串沒有被關閉時，處理器211或回收管理電路單元215會判定此目標區塊串（亦稱，未關閉目標區塊串）的垃圾回收區塊沒有執行完畢，即，對應未關閉目標區塊串的一或多個回收區塊串中的有效資料並沒有全部皆被收集/複製至未關閉目標區塊串中。基此，全域回收區塊串清單中不應該具有未關閉目標區塊串的一或多個回收區塊串，即，在全域回收區塊串清單的恢復操作中，回收管理電路單元215會無視此未關閉目標區塊串的垃圾回收資訊表。應注意的是，在一實施例中，反應於所辨識的未關閉目標區塊串，處理器211或回收管理電路單元215可重新執行對應此目標區塊串的一或多個回收區塊串的垃圾回收操作。
在辨識多個已關閉目標區塊串後，接續至步驟S52，回收管理電路單元215(或回收區塊串記錄電路2152)判斷所述多個已關閉目標區塊串是否皆已被選擇。具體來說，回收管理電路單元215(或回收區塊串記錄電路2152)會開始一個一個地從所述多個已關閉目標區塊串中選擇尚未被選擇的已關閉目標區塊串來執行恢復操作，直到所有已關閉目標區塊串皆被選擇過以執行恢復操作。若存在任何的尚未被選擇的已關閉目標區塊串，接續至步驟S53，回收管理電路單元215(或回收區塊串記錄電路2152)從尚未被選擇的一或多個已關閉目標區塊串中選擇一第一目標區塊串。
接著，在步驟S54中，回收管理電路單元215(或回收區塊串記錄電路2152)辨識所述第一目標區塊串的目標區塊串時間戳記，根據所述第一目標區塊串的垃圾回收資訊表辨識對應所述第一目標區塊串的多個回收區塊串，並且辨識所述多個回收區塊串的回收區塊串時間戳記。具體來說，在選擇第一目標區塊串後，回收管理電路單元215(或回收區塊串記錄電路2152)會根據此第一目標區塊串的區塊串索引值來辨識第一目標區塊串的目標區塊串時間戳記（如，經由讀取系統實體區塊中的對應所述目標區塊串的元資料），並且讀取第一目標區塊串的垃圾回收資訊表。從所讀取的垃圾回收資訊表中，回收管理電路單元215(或回收區塊串記錄電路2152)可辨識到對應第一目標區塊串的多個回收區塊串的回收區塊串索引值，並且根據所述多個回收區塊串索引值來辨識多個回收區塊串的回收區塊串時間戳記（如，經由讀取系統實體區塊中的對應所述多個回收區塊串的元資料）。
接著，在步驟S55中，回收管理電路單元215(或回收區塊串記錄電路2152)比較所述目標區塊串時間戳記與所辨識的多個回收區塊串時間戳記。接著，根據不同的比較結果會進行不同的處置，詳細說明如下。
反應於所辨識的第一回收區塊串時間戳記小於所述目標區塊串時間戳記，接續至步驟S56，回收管理電路單元215(或回收區塊串記錄電路2152) 附加對應第一回收區塊串時間戳記的第一回收區塊串的第一回收區塊串索引值至儲存在緩衝記憶體中的全域回收區塊串清單。
另一方面，反應於所辨識的第二回收區塊串時間戳記大於所述目標區塊串時間戳記，接續至步驟S57，回收管理電路單元215(或回收區塊串記錄電路2152) 不附加對應第二回收區塊串時間戳記的第二回收區塊串的第二回收區塊串索引值至儲存在所述緩衝記憶體中的所述全域回收區塊串清單。即，回收管理電路單元215(或回收區塊串記錄電路2152)認為第二回收區塊串已經在完成對應的垃圾回收操作後又被使用，進而導致第二回收區塊串的第二回收區塊串時間戳記會大於目標區塊串時間戳記。
此外，反應於所辨識的所述多個回收區塊串中的第三回收區塊串的第三區塊串時間戳記為空值（NULL）（如，第三回收區塊串索引值所對應的第三回收區塊串的第三回收區塊串時間戳記並不存在），接續至步驟S58，回收管理電路單元215(或回收區塊串記錄電路2152) 不附加第三回收區塊串的第三回收區塊串索引值至儲存在所述緩衝記憶體中的所述全域回收區塊串清單。
在本實施例中，在第三回收區塊串索引值所對應的第三回收區塊串的第三區塊串時間戳記並不存在或為空值（NULL）的情況下，回收管理電路單元215(或回收區塊串記錄電路2152)可判定所述第三回收區塊串已被執行抹除操作，進而導致所述第三回收區塊串的區塊串時間戳記被刪除。接著，在一實施例中，步驟S58會接續至步驟S60，回收管理電路單元215(或回收區塊串記錄電路2152)可通知處理器211，將所述第三回收區塊串索引值加入至自由區塊串清單。所述自由區塊串清單被維護於緩衝記憶體216中，並且自由區塊串清單所記錄的多個區塊串索引值所對應的多個區塊串皆完成抹除操作。
在所有區塊串時間戳記皆與所述資訊表時間戳記比較且對應比較結果的後續操作（如，步驟S56、S57、S58）也完成後，回收管理電路單元215(或回收區塊串記錄電路2152)完成了對應所選擇的第一目標區塊串的恢復操作。接著，流程會回到步驟S52，即，回收管理電路單元215(或回收區塊串記錄電路2152)會選擇另一個新的尚未被選擇的已關閉目標區塊串來執行恢復操作。
若在步驟S52，回收管理電路單元215(或回收區塊串記錄電路2152)判定所述多個已關閉目標區塊串皆已被選擇，接續至步驟S59，回收管理電路單元215(或回收區塊串記錄電路2152)判定完成全域回收區塊串清單的恢復操作。
值得一提的是，在上述的實施例中，由於垃圾回收操作是針對一或多個回收區塊串所執行，因此垃圾回收資訊表是記錄對應所述一或多個回收區塊串的資訊。但本發明不限於此，例如，在另一實施例中，垃圾回收操作是針對一或多個回收實體區塊所執行，因此垃圾回收資訊表是記錄對應所述一或多個回收實體區塊的資訊。此外，所述垃圾回收資訊表會被寫入至對應一或多個回收實體區塊的目標實體區塊中的最前方。
綜上所述，本發明實施例所提供的記憶體管理方法以及儲存控制器，可僅在反應於開始執行一垃圾回收操作時，根據被執行所述垃圾回收操作的回收區塊串產生垃圾回收資訊表，將所述垃圾回收資訊表寫入至對應所述垃圾回收操作的目標區塊串，再將回收區塊串的有效資料複製至已具有垃圾回收資訊表的所述目標區塊串中，以完成所述垃圾回收操作。此外，在每個目標區塊串中的垃圾回收資訊表也可被用於重建全域回收區塊串清單，以輔助管理儲存裝置整體的區塊串的使用狀況。如此一來，可在減少垃圾回收操作所導致的存取延遲的情況下，依然可以讓儲存裝置所儲存的資料具有可靠性，進而提昇了儲存裝置的工作效率。
雖然本發明已以實施例揭露如上，然其並非用以限定本發明，任何所屬技術領域中具有通常知識者，在不脫離本發明的精神和範圍內，當可作些許的更動與潤飾，故本發明的保護範圍當視後附的申請專利範圍所界定者為準。
10‧‧‧主機系統
20‧‧‧儲存裝置
110、211‧‧‧處理器
120‧‧‧主機記憶體
130‧‧‧資料傳輸介面電路
210‧‧‧儲存控制器
212‧‧‧資料管理電路
213‧‧‧記憶體介面控制電路
214‧‧‧錯誤檢查與校正電路
215‧‧‧垃圾回收管理電路單元
2151‧‧‧垃圾回收執行電路
2152‧‧‧回收區塊串記錄電路
216‧‧‧緩衝記憶體
217‧‧‧電源管理電路
220‧‧‧可複寫式非揮發性記憶體模組
230‧‧‧連接介面電路
S211、S212、S213、S214、S215、S216‧‧‧記憶體管理方法的流程步驟
S221、S222、S223‧‧‧記憶體管理方法的流程步驟
D1‧‧‧封裝
LUN1‧‧‧邏輯數
P1(1)～P1(6)、P1(M-1)、P1(M-1)、P2(1)～P2(6)、P2(M-1)、P2(M)、P3(1)～P3(6)、P3(M-1)、P3(M)、P4(1)～P4(6)、P4(M-1)、P4(M)‧‧‧實體區塊
P1～P4‧‧‧平面
BS(1)～BS(6)、BS(M-1)、BS(M)‧‧‧區塊串
Page[1]~Page[N]‧‧‧實體頁面
400‧‧‧垃圾回收資訊表
410‧‧‧全域回收區塊串清單
DT‧‧‧資料標籤
RBI[1]~RBI[Y]、RBI[1]~RBI[X]‧‧‧區塊串索引值
PD1、PD2‧‧‧填充資料
S51、S52、S53、S54、S55、S56、S57、S58、S59、S60‧‧‧恢復操作的流程步驟
圖1是根據本發明的一實施例所繪示的主機系統及儲存裝置的方塊示意圖。 圖2A是根據本發明的一實施例所繪示的記憶體管理方法的流程圖。 圖2B是根據本發明的一實施例所繪示的記憶體管理方法的流程圖。 圖3為根據本發明的一實施例所繪示的可複寫式非揮發性記憶體模組的多個區塊串的示意圖。 圖4A為根據本發明的一實施例所繪示的垃圾回收資訊表的資料結構的示意圖。 圖4B為根據本發明的一實施例所繪示的寫入垃圾回收資訊表至目標區塊串的示意圖。 圖4C為根據本發明的一實施例所繪示的全域回收區塊串清單的資料結構的示意圖。 圖5是根據本發明的一實施例所繪示的恢復操作的流程圖。

Claims (10)

  1. 一種記憶體管理方法，適用於配置有一可複寫式非揮發性記憶體模組的一儲存裝置，其中該可複寫式非揮發性記憶體模組具有多個實體區塊，並且該些實體區塊被分組為多個區塊串，所述方法包括：執行一垃圾回收指令，其中該垃圾回收指令指示將一或多個回收區塊串的有效資料收集至一目標區塊串；根據所述一或多個回收區塊串產生具有一預定大小的一垃圾回收資訊表，並且將該垃圾回收資訊表寫入至該目標區塊串，其中該垃圾回收資訊表包括一識別標籤、一本地回收區塊串清單與一第一填充資料，其中所述本地回收區塊串清單用以記錄對應所述垃圾回收指令的所述一或多個回收區塊串的一或多個回收區塊串索引值，其中所述一或多個回收區塊串索引值用以表示對應的所述一或多個回收區塊串於該可複寫式非揮發性記憶體模組中的位置；讀取所述一或多個回收區塊串的有效資料，並且將該有效資料寫入至該目標區塊串，其中所寫入的該有效資料緊鄰於被寫入的該垃圾回收資訊表後；以及關閉該目標區塊串，並且將該本地回收區塊串清單附加至一緩衝記憶體中的一全域回收區塊串清單，以完成該垃圾回收指令。
  2. 如申請專利範圍第1項所述的記憶體管理方法，其中在上述將該有效資料寫入至該目標區塊串的步驟後，所述方法記憶體管理方法更包括：反應於判定該目標區塊串具有剩餘空間，將所述剩餘空間寫滿一第二填充資料。
  3. 如申請專利範圍第1項所述的記憶體管理方法，其中該資料標籤在該垃圾回收資訊表的最前方，並且該資料標籤用以表示該資料標籤與位於該資料標籤後的多種資料為具有該預定大小的該垃圾回收資訊表，其中位於該資料標籤後的所述多種資料依序為該本地回收區塊串清單以及該第一填充資料，其中該本地回收區塊串清單用以記錄所述一或多個回收區塊串的回收區塊串索引值，其中該第一填充資料被用以使該垃圾回收資訊表的大小為該預定大小。
  4. 如申請專利範圍第1項所述的記憶體管理方法，更包括：使用一標的區塊串；對照該標的區塊串的標的區塊串索引值與該全域回收區塊串清單所記錄的多個回收區塊串索引值；以及反應於該標的區塊串索引值相符於該些回收區塊串索引值中的一標的回收區塊串索引值，從所述全域回收區塊串清單所記錄的所述多個回收區塊串索引值中刪除所述標的回收區塊串索引值。
  5. 如申請專利範圍第1項所述的記憶體管理方法，更包括：執行對應該全域回收區塊串清單的恢復操作，其中該恢復操作包括：辨識該可複寫式非揮發性記憶體模組的所有目標區塊串中的多個已關閉目標區塊串；判斷該些已關閉目標區塊串是否皆已被選擇，其中反應於判定該些已關閉目標區塊串皆已被選擇，判定完成該全域回收區塊串清單的該恢復操作，其中反應於判定該些已關閉目標區塊串非皆已被選擇，從尚未被選擇的一或多個已關閉目標區塊串中選擇一第一目標區塊串；辨識該第一目標區塊串的一目標區塊串時間戳記，根據該第一目標區塊串的垃圾回收資訊表辨識對應該第一目標區塊串的多個回收區塊串，並且辨識該些回收區塊串的一回收區塊串時間戳記；比較該目標區塊串時間戳記與所辨識的多個回收區塊串時間戳記，其中反應於所辨識的第一回收區塊串時間戳記小於該目標區塊串時間戳記，附加對應該第一回收區塊串時間戳記的一第一回收區塊串的一第一回收區塊串索引值至儲存在該緩衝記憶體中的該全域回收區塊串清單，其中反應於所辨識的一第二回收區塊串時間戳記大於該目標區塊串時間戳記，不附加對應該第二回收區塊串時間戳記的一第二回收區塊串的一第二回收區塊串索引值至儲存在該緩衝記憶體中的該全域回收區塊串清單，其中反應於所辨識的該些回收區塊串中的一第三回收區塊串的一第三區塊串時間戳記為空值，不附加該第三回收區塊串的一第三回收區塊串索引值至儲存在該緩衝記憶體中的該全域回收區塊串清單。
  6. 一種儲存控制器，用於控制配置有一可複寫式非揮發性記憶體模組的一儲存裝置，該儲存控制器包括：一連接介面電路，用以耦接至一主機系統；一記憶體介面控制電路，用以耦接至該可複寫式非揮發性記憶體模組，其中該可複寫式非揮發性記憶體模組具有多個實體區塊，並且該些實體區塊被分組為多個區塊串；一垃圾回收管理電路單元；以及一處理器，耦接至該連接介面電路、該記憶體介面控制電路及該垃圾回收管理電路單元，其中該垃圾回收管理電路單元用以執行從該處理器所接收的一垃圾回收指令，其中該垃圾回收指令指示將一或多個回收區塊串的有效資料收集至一目標區塊串，其中該垃圾回收管理電路單元更用以根據所述一或多個回收區塊串產生具有一預定大小的一垃圾回收資訊表，並且指示該記憶體介面控制電路將該垃圾回收資訊表寫入至該目標區塊串，其中該垃圾回收資訊表包括一識別標籤、一本地回收區塊串清單與一第一填充資料，其中所述本地回收區塊串清單用以記錄對應所述垃圾回收指令的所述一或多個回收區塊串的一或多個回收區塊串索引值，其中所述一或多個回收區塊串索引值用以表示對應的所述一或多個回收區塊串於該可複寫式非揮發性記憶體模組中的位置，其中該垃圾回收管理電路單元更用以指示該記憶體介面控制電路讀取所述一或多個回收區塊串的有效資料，並且指示該記憶體介面控制電路將該有效資料寫入至該目標區塊串，其中所寫入的該有效資料緊鄰於被寫入的該垃圾回收資訊表後，其中該垃圾回收管理電路單元更用以指示該記憶體介面控制電路關閉該目標區塊串，並且該垃圾回收管理電路單元更用以將該本地回收區塊串清單附加至一緩衝記憶體中的一全域回收區塊串清單，以完成該垃圾回收指令。
  7. 如申請專利範圍第6項所述的儲存控制器，其中在上述將該有效資料寫入至該目標區塊串的運作後，反應於判定該目標區塊串具有剩餘空間，該垃圾回收管理電路單元指示該記憶體介面控制電路將所述剩餘空間寫滿一第二填充資料。
  8. 如申請專利範圍第6項所述的儲存控制器，其中該資料標籤在該垃圾回收資訊表的最前方，並且該資料標籤用以表示該資料標籤與位於該資料標籤後的多種資料為具有該預定大小的該垃圾回收資訊表，其中位於該資料標籤後的所述多種資料依序為該本地回收區塊串清單以及該第一填充資料，其中該本地回收區塊串清單用以記錄所述一或多個回收區塊串的回收區塊串索引值，其中該第一填充資料被用以使該垃圾回收資訊表的大小為該預定大小。
  9. 如申請專利範圍第6項所述的儲存控制器，其中該處理器使用一標的區塊串，其中該垃圾回收管理電路單元該對照該標的區塊串的標的區塊串索引值與該全域回收區塊串清單所記錄的多個回收區塊串索引值，反應於該標的區塊串索引值相符於該些回收區塊串索引值中的一標的回收區塊串索引值，該垃圾回收管理電路單元從所述全域回收區塊串清單所記錄的所述多個回收區塊串索引值中刪除所述標的回收區塊串索引值。
  10. 如申請專利範圍第6項所述的儲存控制器，其中該處理器更指示該垃圾回收管理電路單元執行對應該全域回收區塊串清單的恢復操作，其中該恢復操作包括：該垃圾回收管理電路單元辨識該可複寫式非揮發性記憶體模組的所有目標區塊串中的多個已關閉目標區塊串，其中該垃圾回收管理電路單元判斷該些已關閉目標區塊串是否皆已被選擇，其中反應於判定該些已關閉目標區塊串皆已被選擇，該垃圾回收管理電路單元判定完成該全域回收區塊串清單的該恢復操作，其中反應於判定該些已關閉目標區塊串非皆已被選擇，該垃圾回收管理電路單元從尚未被選擇的一或多個已關閉目標區塊串中選擇一第一目標區塊串，其中該垃圾回收管理電路單元辨識該第一目標區塊串的一目標區塊串時間戳記，根據該第一目標區塊串的垃圾回收資訊表辨識對應該第一目標區塊串的多個回收區塊串，並且辨識該些回收區塊串的一回收區塊串時間戳記，其中該垃圾回收管理電路單元比較該目標區塊串時間戳記與所辨識的多個回收區塊串時間戳記，其中反應於所辨識的第一回收區塊串時間戳記小於該目標區塊串時間戳記，該垃圾回收管理電路單元附加對應該第一回收區塊串時間戳記的一第一回收區塊串的一第一回收區塊串索引值至儲存在該緩衝記憶體中的該全域回收區塊串清單，其中反應於所辨識的一第二回收區塊串時間戳記大於該目標區塊串時間戳記，該垃圾回收管理電路單元不附加對應該第二回收區塊串時間戳記的一第二回收區塊串的一第二回收區塊串索引值至儲存在該緩衝記憶體中的該全域回收區塊串清單，其中反應於所辨識的該些回收區塊串中的一第三回收區塊串的一第三區塊串時間戳記為空值，該垃圾回收管理電路單元不附加該第三回收區塊串的一第三回收區塊串索引值至儲存在該緩衝記憶體中的該全域回收區塊串清單。
TW107126694A 2018-08-01 2018-08-01 記憶體管理方法以及儲存控制器 TWI671631B (zh)

Priority Applications (2)

Application Number Priority Date Filing Date Title
TW107126694A TWI671631B (zh) 2018-08-01 2018-08-01 記憶體管理方法以及儲存控制器
US16/137,539 US10642731B2 (en) 2018-08-01 2018-09-20 Memory management method and storage controller

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
TW107126694A TWI671631B (zh) 2018-08-01 2018-08-01 記憶體管理方法以及儲存控制器

Publications (2)

Publication Number Publication Date
TWI671631B true TWI671631B (zh) 2019-09-11
TW202008168A TW202008168A (zh) 2020-02-16

Family

ID=68618963

Family Applications (1)

Application Number Title Priority Date Filing Date
TW107126694A TWI671631B (zh) 2018-08-01 2018-08-01 記憶體管理方法以及儲存控制器

Country Status (2)

Country Link
US (1) US10642731B2 (zh)
TW (1) TWI671631B (zh)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111880749A (zh) * 2020-08-04 2020-11-03 群联电子股份有限公司 数据读取方法、存储器存储装置及存储器控制电路单元

Families Citing this family (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US11514027B2 (en) * 2019-06-07 2022-11-29 Sap Se Paged hybrid LOBs
CN113641597B (zh) * 2020-04-27 2024-07-12 慧荣科技股份有限公司 管理数据存储的方法及装置以及计算机可读取存储介质
TWI797464B (zh) * 2020-07-28 2023-04-01 群聯電子股份有限公司 資料讀取方法、記憶體儲存裝置及記憶體控制電路單元
CN113096713B (zh) * 2021-04-12 2024-05-07 合肥兆芯电子有限公司 存储器管理方法、存储器控制电路单元与存储器存储装置
US11543993B1 (en) * 2021-06-17 2023-01-03 Western Digital Technologies, Inc. Fast garbage collection in zoned namespaces SSDs
KR20240116019A (ko) * 2023-01-20 2024-07-29 에스케이하이닉스 주식회사 컨트롤러, 스토리지 장치 및 테스트 시스템

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
TW201510723A (zh) * 2009-09-03 2015-03-16 Pioneer Chip Technology Ltd 以頁面為基礎管理快閃儲存裝置
TWI613652B (zh) * 2017-03-27 2018-02-01 慧榮科技股份有限公司 資料儲存裝置以及其操作方法
TWI621018B (zh) * 2017-07-24 2018-04-11 大陸商深圳大心電子科技有限公司 資料備份方法、資料恢復方法以及儲存控制器
TWI629592B (zh) * 2017-10-25 2018-07-11 旺宏電子股份有限公司 記憶體裝置及應用於其上之資料管理方法

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
TW201510723A (zh) * 2009-09-03 2015-03-16 Pioneer Chip Technology Ltd 以頁面為基礎管理快閃儲存裝置
TWI613652B (zh) * 2017-03-27 2018-02-01 慧榮科技股份有限公司 資料儲存裝置以及其操作方法
TWI621018B (zh) * 2017-07-24 2018-04-11 大陸商深圳大心電子科技有限公司 資料備份方法、資料恢復方法以及儲存控制器
TWI629592B (zh) * 2017-10-25 2018-07-11 旺宏電子股份有限公司 記憶體裝置及應用於其上之資料管理方法

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111880749A (zh) * 2020-08-04 2020-11-03 群联电子股份有限公司 数据读取方法、存储器存储装置及存储器控制电路单元
CN111880749B (zh) * 2020-08-04 2023-06-13 群联电子股份有限公司 数据读取方法、存储器存储装置及存储器控制电路单元

Also Published As

Publication number Publication date
US20200042441A1 (en) 2020-02-06
TW202008168A (zh) 2020-02-16
US10642731B2 (en) 2020-05-05

Similar Documents

Publication Publication Date Title
TWI671631B (zh) 記憶體管理方法以及儲存控制器
TWI679537B (zh) 資料移動方法及儲存控制器
TWI480733B (zh) 資料寫入方法、記憶體控制器與記憶體儲存裝置
TWI515735B (zh) 資料抹除方法、記憶體控制電路單元及記憶體儲存裝置
TWI579696B (zh) 資料重建方法與系統及其記憶體控制電路單元
TWI592799B (zh) 映射表更新方法、記憶體控制電路單元及記憶體儲存裝置
TWI479505B (zh) 資料管理方法、記憶體控制器與記憶體儲存裝置
TWI421683B (zh) 資料管理方法、記憶體控制器與記憶體儲存裝置
TWI676176B (zh) 資料整併方法、記憶體儲存裝置及記憶體控制電路單元
TW201947402A (zh) 記憶體管理方法以及儲存控制器
TWI695263B (zh) 記憶體管理方法以及儲存控制器
TW201944421A (zh) 平均磨損方法、記憶體控制電路單元與記憶體儲存裝置
CN110825310B (zh) 存储器管理方法以及存储控制器
TW202201229A (zh) 記憶體控制方法、記憶體儲存裝置及記憶體控制電路單元
TWI509615B (zh) 資料儲存方法、記憶體控制器與記憶體儲存裝置
TWI651650B (zh) 記憶體管理方法及使用所述方法的儲存控制器
TWI712052B (zh) 記憶體管理方法、儲存控制器與儲存裝置
CN114203239B (zh) 存储器管理方法、存储器存储装置及存储器控制电路单元
TW201820114A (zh) 資料寫入方法以及儲存控制器
TWI766582B (zh) 有效資料合併方法、記憶體儲存裝置及記憶體控制電路單元
CN119396337B (zh) 存储器管理方法以及存储器存储装置
CN110825653B (zh) 存储器管理方法以及存储控制器
TW201643722A (zh) 記憶體管理方法、記憶體控制電路單元及記憶體儲存裝置
TWI621018B (zh) 資料備份方法、資料恢復方法以及儲存控制器
TWI762843B (zh) 儲存控制器、記憶體管理方法與儲存裝置