Tata Elxsi Limited, Bangalore, India April 29, 2009
Background of the Invention
Field of the Invention
The present disclosure relates to the flash memories in particular to NAND flash memories, a method of managing bad blocks and wears leveling in the controller hardware.
Description of the Related Art
Flash memory becoming popular for storage media. Due to its unique characteristics of flash memory, the management of flash memory as a storage system is much different from those based on main memory and disks. In particular, NAND flash memory is write - once such that updates to existing data on a page are only possible after an erase operation. Data must be written to free space, and the old versions; of data are invalidated. Therefore, available free space on flash memory could become |low after a number of writes, which demands frequent ■ activities in the recycling of available space on flash memory from time to time. Hence handling the endurance of the NAND flash with out
loosing system performance and cost has become the challenge in today's NAND flash
■i
controller development. Also -bad blocks are available while shipping from the
manufacturer and developed during the life-time of the flash. So handling these bad
blocks become the one of the task during flash management. i
■' !
■ '. 'I
The Patent entitled 'Flash memory device for performing bad block management and method of performing bad block management of flash memory device' [US 7434122 B2] describes the bad block management in hardware to handle the flash memory bad blocks
by checking the logical block address requested by the external device with the preloaded
" - ■ if
bad block lookup table.
i The Patent entitled 'NAND flash memory management' [US 7366825 B2] describes the
ii
bad block management in hardware to handle the flash memory |bad blocks by dividing
the flash memory to set of main: block memory and auxiliary memory. Storing the bad
i
block information in good block rheta data as block identifier.

Tata Elxsi Limited, Bangalore, India April 29, 2009
The Patent entitled 'Wear leveling in storage devices based on flash memories and related circuit, system, and method' [US2 008/028202 5 AIJ describes the method of reducing the wear of the flash memory by distributing the data across the memory with out erasing blocks till it reaches the threshold value of free blocks. Erasing of the physical blocks happens only after reaching the threshold value of the available free block.
However, with reference to the above-mentioned work, the present embodiment proposes a method to handle bad block management and wear leveling with high performance and cost effective in hardware.
Summary of the Invention
The present invention is target to address the bad block management and wear leveling of
the flash in hardware with out loosing the performance of the flash during write or read
operation. This is achieved by creating the flash management table (FMT) with
i appropriate mapping logic, bad block management and free block pool for wear leveling.
i
In accordance with the present invention during the power on process the flash controller
i
scans the first page of the every block of the flash and creates the FMT as per the
mapping logic invented. Bad block management is performed oh the FMT and changes
dll-the logical bad blocks to good blocks as per the present invention. Another entity of
the present invention is wear leveling for evenly distribution of flash memory blocks
i during the page program operation. To achieve this, free block pool table is maintained in
the order of their least wear level values. So that for any page program request to free
block in the flash, the controller picks block from free block pool. ■
Brief Description of Accompanying Drawings
FIGURE 1 shows the block level diagram of flash management to perform bad block management and wear leveling in accordance with the present invention.
FIGURE 2 shows the organization of page inside a block into data area 201 and spare area 202.
13

Tata Elxsi Limited, Bangalore, India April 29, 2009
FIGURE 3 shows the block level diagram of Power on process in accordance with the present invention.
FIGURE 4 shows the flows chart for FMT creation in accordance with the present invention.
i i
FIGURE 5 shows the flow chart for Wear leveling in accordance with the present invention.
FIGURE 6 shows the flow chart for flash device command execution performed by central processing unit 101 in accordance with the present invention.
FIGURE 7a shows an example of flash management data stored in the spare area of flash memory in accordance with the current invention.
FIGURE 7b shows the creation of FMT on power-up from the flash management information provided in FIG 7a in accordance with the current invention.
FIGURE 7c shows the bad block mapping logic followed by ;;FMT creation in accordance with the current invention.
FIGURE 7d shows the free block pool table creation in accordance with the current invention.
FIGURE 8a shows the FMT data after write LBA 3 operation in accordance with current invention.
FIGURE 8b shows the flash memory spare area data after write LBA 3 operation in accordance with the current invention.

Tata Elxsi Limited, Bangalore, India

April 29, 2009

FIGURE 8c shows the free block pool table after write LBA 3 operation in accordance with the current invention.
FIGURE 9a shows the FMT data after erase LBA 0 operation in accordance with the current invention.
FIGURE 9b shows the flash memory spare area data after Erase LBA 0 operation in accordance with the current invention.
FIGURE 9c shows the free block pool table after erase LBA 0 operation in accordance with the current invention.
Detailed Description of the Invention with Reference to Accompanying Drawings
FIGURE 1 shows the block diagram of flash management to perform bad block management and wear leveling in accordance with the present invention. As shown in the figure the flash management module 100 consist of bad block management module 106, wear leveling module 105, free block pool memory 102 (holds the LBA of free blocks), FMT RAM 103 (holds flash management information), power on prbcess module 104 and central processing module 101. Central processing module will control all the modules and handles flash device operations.
FIGURE 2 shows the organization of page inside a block into data area 201 and spare area 202. In accordance with the present invention the spare area 202 is used to store the flash management information, which includes bad block pointer, block used, LBA, ECC data, Meta data, page used and Wear leveling count.
FIGURE 3 shows the block level diagram of Power on process in accordance with the
present invention. Power on process 300 consists of mapping logic 303, read spare logic
i
302, framing logic 304, and PBA generator 301 to create FMT. PBA generator 301 generates the address of the block, to perform read operation.! Read spare logic 302

Tata Elxsi Limited, Bangalore, India

April 29, 2009

performs read the spare data of the flash. Framing logic 304 along with mapping logic 303 frames the spare data received from 302 and stores it in FMTJ
FIGURE 4 shows the flows chart for FMT creation in accordance with the present invention. After power-on reset the power on process 300 FIG 3 checks if FMT is created
402. If FMT is not created the process starts reading the flash memory 1st page spare area
of every block, frames the data and creates FMT in step 403. After FMT creation in step
403, Bad block management module 106 reads the FMT data in step 404, checks the BBP
bit in step 405, if bit is equal to 1 and LBA accessed is not the last block in step 408 LBA
is incremented in step 409 and goes to step 404. In step 405, if BBP bit is equal to 0
assigns a free block from reserved memory in step 406, updates the FMT with the
mapping information in step 407 and goes to step 408. In step 408, if the LBA accessed is
the last block, then it goes to FMT creation done in step 410.
FIGURE 5 shows the flow chart for Wear leveling in accordance with the present invention. After power on reset it goes to step 502 from idle state in step 501 where it waits till FMT creation is done in step 410. On FMT creation done it goes to step 503 where it compare the wear leveling count of all blocks sequentially, stores the least wear leveling count LBA's in free block pool memory in step 504 and goes to step 505 where it waits for write operation equal to 1. It repeats the process starting from step 503 during every write operation as per the invention.
FIGURE 6 shows the flow chart for flash device command execution performed by central processing unit 101 in accordance with the present invention. In step 601 it waits for command from host. When command is received it goes to step 602 where it checks whether the command is write/read/erase. If it is a write command, it goes the LBA location in FMT in step 603 checks the BU bit in step 604. If BU:is set to 0 it fetches the physical address in step 605, performs the write operation in step 606 and checks for yvfite status in step 607. If the write status is equal to 0 then it performs bad block management 106 in step 608 and sends write fail info to host in step 609. If write status is equal to 1 it goes to step 601. In step 604, if BU is equal to 1, it gets the LBA from free

Tata Elxsi Limited, Bangalore, India April 29, 2009
block pool table, fetches the PBA from FMT in step 610, updates the FMT in step 611
and goes to step 606. In step 602 if the command received is read/erase, it goes to LBA
location in FMT in step 612, and then checks the BU bit in step 613. If BU is set to 1 it
i.
fetches the physical address in step 614 performs read/erase operation in step 615 and
checks for read/erase status in step 616. If read/erase status is equal to 0 it goes to step
608 and if status is equal to 1 it goes to step 601.
FIGURE 7a shows an example of flash management data stored in the spare area of
flash memory in accordance with the current invention. Block addresses (PBA) 0, 1,5, 7,
8 are free blocks in user area and 1022, 1023 are free blocks in reserved area. Hence the
fields in the flash spare area are all l's except WLC. Blocks 2 and 6 are bad blocks
i indicated by BBP byte. Blocks 3, 4 and 1021 are used blocks mapped to blocks (LBA) 7,
0 and 2 and respective fields are set.
v
FIGURE 7b shows the creation of FMT on power-up from the flash management
information provided in FIG 7a in accordance with the current invention. FMT is indexed
by LBA. As per the current invention the mapping logic 303 maps all the used LBA's to
corresponding PBA's from the flash management data retrieved. All the free LBA's are
mapped to free PBA's as per the current invention.
FIGURE 7c shows the bad block mapping logic followed by FMT creation in accordance with the current invention. LBA 2 is already used and is mapped to 1021. LBA 6 is a bad block and is mapped to 1022, which is a free block in reserved area.
FIGURE 7d shows the free block pool table creation in accordance with the current invention. Wear leveling module 105 creates the free block pool table by sequentially checking the wear level count of each block and stores the LBA's with least count.
FIGURE 8a shows the FMT data after write LBA 3 operation in accordance with current invention. Mapping logic 303 when receives the write command for LBA 3, it checks whether the block used (BU) bit is set. As BU bit in FMT for LBA 3 is l, it takes the new

Tata Elxsi Limited, Bangalore, India April 29, 2009
LBA from free block pool table, which is 1. Mapping logic goes to LBA 1, takes the PBA that is 1 and writes the data to PBA 1. It updates the FMT by swapping the BU, PBA and WLC data between LBA 3 and 1.
FIGURE 8b shows the flash memory spare area data after write LBA 3 operation in accordance with the current invention. PBA 1 consists of LBA 3 information.
FIGURE 8c shows the free block pool table after write LBA 3 operation in accordance with the current invention.
FIGURE 9a shows the FMT data after erase LBA 0 operation ,in accordance with the current invention. Mapping logic 303 when receives the erase cbmmand for LBA 0, it checks whether the block used (BU) bit is set. As BU bit in FMTiFIG 8a for LBA 3 is 0, it takes the corresponding PBA in FMT, which is 4 sends command to erase PBA 4. It updates the FMT by changing the BU bit to 1 in LBA 0.
FIGURE 9b shows the flash memory spare area data after Erase LBA 0 operation in accordance with the current invention. PBA 4 consists of all 1 's.
FIGURE 9c shows the free block pool table after erase LBA 0 operation in accordance with the current invention. LBA 0 is added in top of free block pool table, as its wear ievel count is the least.
Terminology
1. FMT; Flash Management table used to store the flash information during the
power ON.
i
2. LBA: Logical Block Address is the block address requested by host.
3. PBA: Physical Block Address is the block address of the flash where actual data is stored.
. 4. WLC: Wear Level Count is the number of erases on the block. >5. BBP: Bad block Pointer is used to indicate the whether the block is bad are good.

Tata Elxsi Limited, Bangalore, India April 29, 2009
6. BU: Block used bit /Byte to indicate whether the block is used or not.
7. PU: Page used bit/byte to indicate whether the page is used or not.
8. Free block pool: A pool of free logical blocks arranged in the order of their least wear level values.
Industrial Applicability
• The demand for NAND Flash memory is growing at a phenomenal rate as the inclusion of NAND Flash in an increasing number of hand held devices like MP3 players, high-end cell phones and digital cameras has fueled expectations that NAND will overtake NOR in a number of markets.
• Rapid increases in the capacity of NAND flash, coupled with mobile consumer products that demand ever-increasing amounts of data storage, lay out a very bright future for this technology in coming years.
• The present inventions address the above-mentioned industries for better solution in terms of data integrity, endurance and performance in flash storage.

Claims
1. A method of using flash memory device spare area for storing flash management information which comprises
a. Bad block pointer, logical address if the physical block is mapped to some
other block, wear leveling count, block used bit and page used bit.
b. The method of storing the flash management information in 1st page of
every block and page used information in all pages of every block.

Tata Elxsi Limited, Bangalore, India April 29, 2009
2. The method of creating flash management table (FMT) in flash controller after
power on reset comprising
a. Reading the 1st page spare area of every block, mapping the blocks in
accordance with logical block address present in the flash management
information of spare area in accordance with present invention 303.
b. Mapping the bad blocks to free blocks in reserved area and updating the
mapping information in FMT.
3. The method of creating a free block pool table after FMT creation by checking the
wear level count of every block in FMT and placing the logical block address of
the block which has least wear level count into free block pool table and also
updating the free block pool table during busy time of ;the page programming
operation.
4. The method of mapping the logical address to physical address from FMT during
write operation.
5. The method of mapping the logical address to physical address; from FMT during
read/erase operation.