System and method for managing trim operations in a flash memory system using mapping tables and block status tables

• US 9,323,667 B2
• Filed: 04/10/2013
• Issued: 04/26/2016
• Est. Priority Date: 04/12/2012
• Status: Active Grant

• Current Assignee: Innovations In Memory LLC
• Original Assignee: Violin Memory Incorporated
• Inventors: Bennett, Jon C.R.
• Primary Examiner(s): Thai, Tuan
• Assistant Examiner(s): Gossage, Glenn
• Application Number:
  US13/860,118
• Publication Number:
  US 20130275660A1
• Time in Patent Office: 1,112 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0292 using tables or multilevel address translation means G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10
• CPC Class Codes: G06F 16/1847 specifically adapted to static storage, e.g. adapted to flash memory or SSD
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7209 Validity control, e.g. using flags, time stamps or sequence numbers

Abstract

A method and system for managing a flash memory system facilitates the use of TRIM or similar operations so as to release physical memory space of logical block addresses (LBAs) that are declared to be deleted by a user file management system. A plurality of data structures corresponding to levels of indirection are used to manage the mapping between a user logical block address and the physical location of the data in the flash memory system and to respond to user read and write requests by determining the current status of the user logical block address in the frame of reference of the memory system. This process substantially decouples TRIM management from garbage collection and wear leveling operations.

Claims

1. A method of managing a flash memory comprising:

providing a controller configured to;

maintain a first table mapping between a user logical address and a physical address where data is stored in the flash memory;

maintain a second table indicating a status for each physical address of a block of physical addresses;

maintain a third table representing a user initiated data invalidation operation of the user logical address;

wherein the controller is further operative for;

accepting a user initiated data invalidation command for the user logical address; and

updating the first, the second, and the third tables to show the status of an invalid logical and physical data address as invalid;

receiving a read request from a user and;

using an entry in the third table to determine if the user logical address corresponds to an entry in the second table that is valid or invalid; and

if the entry in the third table is invalid, return a value determined by a protocol;

or,

if the entry in the third table is valid;

 

using the first table to retrieve data

corresponding to the read request from the physical address;

receiving a write request from a user and;

using the entry in the third table to determine if the user logical address corresponds to an entry in the second table that is valid or invalid; and

if the entry in the third table is valid, writing data corresponding to the user logical address of the write request to a physical address allocated by the second table;

or

if the entry in the third table corresponding to the user logical address of the write request is invalid, updating the entry in the third table to valid; and

 

writing data corresponding to the user logical address of the write request to a physical address allocated using the second table.

2. A non-transitory computer readable memory storing a computer program product, comprising:

instructions for configuring a controller to;

maintain a first table mapping between a user logical address and a physical address where data is stored in flash memory;

maintain a second table indicating a status for each physical address of a block of physical addresses;

maintain a third table representing a user initiated data invalidation operation of the user logical address;

wherein the controller is further operative for;

accepting a user initiated data invalidation command for the user logical address; and

updating the first, the second, and the third tables to show the status of invalid logical and physical data addresses as invalid;

receiving a read request from a user and;

using an entry in the third table to determine if the user logical address corresponds to a second table entry that is valid or invalid; and

if the entry in the third table is invalid, return a value determined by a protocol;

or,

if the entry in the third table is valid, using the first table to retrieve data corresponding to the read request from the physical address;

receiving a write request from a user and;

using the entry in the third table to determine if the user logical address corresponds to an entry in the second table that is valid or invalid; and

if the entry in the third table is valid, writing data corresponding to the user logical address of the write request to a physical address allocated by the second table;

or

if the entry in the third table entry-corresponding to the user logical address of the write request is invalid;

updating the entry in the third table to valid; and

writing data corresponding to the user logical address of the write request to a physical address allocated using the second table.