CN103226517A

CN103226517A - Method for dynamically ordering physical blocks of Nandflash according to quantity of invalid pages

Info

Publication number: CN103226517A
Application number: CN2012100218375A
Authority: CN
Inventors: 迟志刚
Original assignee: Shanghai Huahong Integrated Circuit Co Ltd
Current assignee: Shanghai Huahong Integrated Circuit Co Ltd
Priority date: 2012-01-31
Filing date: 2012-01-31
Publication date: 2013-07-31

Abstract

The invention discloses a method for dynamically ordering physical blocks of Nandflash according to the quantity of invalid pages. The method comprises the steps as follows: step one, an updated physical block is deleted from the original position, and physical blocks in front and at the back of the updated physical block are reconnected; and step two, the updated physical block is inserted into a new position of an ordering linked list again. The method can effectively shorten the time which is consumed by searching the physical block with the maximum quantity of invalid pages.

Description

The physical block of Nandflash is carried out the method for dynamic order by invalid number of pages amount

Technical field

The present invention relates to a kind of method of the physical block of Nandflash (with NOT-AND flash) being carried out dynamic order by invalid number of pages amount.

Background technology

Nandflash has obtained the development of advancing by leaps and bounds in recent years, to MLC (multidigit/unit) technology, the production technology of Nandflash is also constantly progressive simultaneously by SLC (1/unit) technical development.Along with the development of technology, the Nandflash capacity constantly increases, and the cost of unit capacity also significantly reduces, and the field of using Nandflash is also more and more.

The erasable number of times of Nandflash is limited, will wipe the maximum piece of invalid number of pages amount in erasable as far as possible, therefore in the design of Nandflash controller, selects the maximum piece of invalid number of pages amount, is a very necessary function.

When each rubbish piece reclaimed, the way of general Nandflash controller all needed from the beginning to search the maximum piece of invalid number of pages amount, and this needs considerable time.

Summary of the invention

The technical problem to be solved in the present invention provides a kind of physical block to Nandflash and carries out the method for dynamic order by invalid number of pages amount, can effectively shorten and search invalid maximum time that piece spent of number of pages amount.

For solving the problems of the technologies described above, the method that the physical block of Nandflash is carried out dynamic order by invalid number of pages amount of the present invention comprises the steps:

The first step is deleted the physical block that is updated from original position, the physical block before and after it is reconnected;

In second step, the physical block that is updated is inserted into again in the reposition of ordering chained list.

Described ordering chained list adopts list structure.

When the invalid number of pages amount of physical block changes, immediate updating ordering chained list.

After system powers on, need be before carrying out write operation, described Nandflash physical block sorted by invalid number of pages amount generates the ordering chained list.

The present invention is on the basis of invalid number of pages amount in each physical block of known Nandflash, adopt the ordering list structure that the physical block of Nandflash is carried out dynamic order, by dynamically updating the ordering chained list when the write operation, shortened greatly and searched invalid maximum time that physical block spent of number of pages amount.

Adopt method of the present invention, by the dynamically updating of the ordering chained list of invalid number of pages amount, only need several operations to finish the physical block of Nandflash, the system time cost is very little.

When the rubbish piece reclaimed, system can directly read the physical block of Nandflash by first physical block in the ordering chained list of invalid number of pages amount ordering, can obtain the maximum physical block of invalid number of pages amount, has significantly reduced the system time cost.

Description of drawings

The present invention is further detailed explanation below in conjunction with accompanying drawing and embodiment:

Accompanying drawing is that the physical block of Nandflash is dynamically updated process flow diagram by the ordering chained list of invalid number of pages amount ordering.

Embodiment

After system powers on, need be before carrying out write operation, the physical block of Nandflash is carried out initialization by the ordering chained list of invalid number of pages amount ordering.Initialized effect is according to invalid number of pages amount contained in each physical block, generates the ordering chained list.

Shown in accompanying drawing, when contained invalid number of pages amount increases in a physical block, just begin more new sort chained list.For example, when the invalid number of pages of physical block M is updated to N+1 by N, the physical block M that is updated is deleted from original position, and last physical block and back one physical block of physical block M is together in series; Upgrade correlated variables (as GRP_N+1_HP, GRP_N_HP and TAIL) then.Physical block M is inserted into the reposition of ordering in the chained list, and then upgrades correlated variables (as GRP_N+1_HP, GRP_N_HP and HELD).

The definition of each variable sees the following form 1 among the present invention:

Table 1

The ordering list structure that the physical block of Nandflash is sorted, for each physical block corresponding catena is arranged all, each comprises two pointers, a previous physical block that points to current physical block, and another points to a back physical block of current physical block.Each physical block all has 4 bytes in chained list, its implication is as shown in table 2 below:

Table 2

Like this ordering of physical block has just been become PBP and the NBP of each in the ordering chained list carried out assignment.

It is four types that physical block deletion from the ordering chained list is divided into:

The 1st type, physical block M is HEAD, and step is as follows:

Are step 1, the invalid number of pages of judgement physical block HEAD.NBP N? If then forward step 2 to, execution in step three then if not.

Step 2, finish following assignment successively, finish then;

To the GR_N+1_HP assignment is M;

To the GRP_N_HP assignment is HEAD.NBP.

Step 3, finish following assignment successively, finish then;

To the GRP_N+1_HP assignment is M;

To the GRP_N_HP assignment is NULL.

The 2nd kind is not that the 1st type and physical block M are TAIL, comprises the steps:

Step 1, judge whether GRP_N_HP is M, if execution in step 2 then, if not, then execution in step 3.

Step 2, judge whether GRP_N+1_HP is NULL,, if not, then forward step 5 to if forward step 4 to.

Step 3, finish following assignment successively, finish then;

To the TAIL assignment is M.PBP;

To the M.PBP.NBP assignment is NULL.

Step 4, finish following assignment successively, finish then;

To the GRP_N+1_HP assignment is M;

To the GRP_N_HP assignment is NULL.

Step 5, finish following assignment successively, finish then;

To the TAIL assignment is M.PBP;

To the M.PBP.NBP assignment is NULL;

To the GRP_N_HP assignment is NULL.

The 3rd kind is not the 1st type and the 2nd type, and physical block M is GRP_N_HP, and step is as follows:

The first step, the invalid number of pages of judgement physical block M.NBP are N, if forwarded for second step to, forward for the 3rd step if not to.

Second goes on foot, finishes successively following assignment, finishes then;

To the M.PBP.NBP assignment is M.NBP;

To the M.NBP.PBP assignment is M.PBP;

To the GRP_N_HP assignment is M.NBP.

The 3rd the step, judge whether GRP_N+1_HP is NULL, if forwarded for the 4th step to, if not, forwarded for the 5th step to.

The 4th goes on foot, finishes successively following assignment, finishes then;

To the GRP_N_HP assignment is NULL;

To the GRP_N+1_HP assignment is M.

The 5th goes on foot, finishes successively following assignment, finishes then;

To the GRP_N_HP assignment is NULL;

To the M.PBP.NBP assignment is M.NBP;

To the M.NBP.PBP assignment is M.PBP.

The 4th type is the 1st type, and the type outside the 2nd type and the 3rd type is finished following assignment successively, finishes then;

To the M.PBP.NBP assignment is M.NBP;

To the M.NBP.PBP assignment is M.PBP.

With physical block insert the ordering chained list operate in the operation that physical block deletes from the ordering chained list after carry out, also be divided into four types.

First type, N equals PN-1, need finish following assignment successively:

To the HEAD.PBP assignment is M;

To the M.NBP assignment is HEAD;

To the M.PBP assignment is NULL;

To the HEAD assignment is M.

Second type, non-first type and GRP_N+1_HP equals HEAD or GRP_N_HP equals HEAD, need finish following assignment successively:

To the HEAD.PBP assignment is M;

To the M.NBP assignment is HEAD;

To the M.PBP assignment is NULL;

To the HEAD assignment is M;

To the GRP_N+1_HP assignment is M.

The third type, non-first type and second type and GRP_N+1_HP are not equal to NULL.Need finish following assignment successively:

To the GRP_N+1_HP.PBP.NBP assignment is M;

To the M.PBP assignment is GRP_N+1_HP.PBP;

To the M.NBP assignment is GRP_N+1_HP;

To the GRP_N+1_HP.PBP assignment is M;

To the GRP_N+1_HP assignment is M.

The 4th type is the type outside first type, second type and the third type, need finish following assignment successively:

To the GRP_N_HP.PBP.NBP assignment is M;

To the M.PBP assignment is GRP_N_HP.PBP;

To the M.NBP assignment is GRP_N_HP;

To the GRP_N_HP.PBP assignment is M;

To the GRP_N+1_HP assignment is M.

The present invention adopts list structure that the Nandflash physical block is sorted, and the ordering chained list is in case foundation has write operation just to dynamically update at every turn.When needs were searched the maximum piece of invalid number of pages amount, first physical block of searching the ordering chained list got final product, and searches invalid maximum time that piece spent of number of pages amount thereby shortened greatly.

More than by embodiment the present invention is had been described in detail, but these are not to be construed as limiting the invention.Under the situation that does not break away from the principle of the invention, those skilled in the art also can make many distortion and improvement, and these also should be considered as protection scope of the present invention.

Claims

1. one kind to carrying out the method for dynamic order with the physical block of NOT-AND flash Nandflash by invalid number of pages amount, it is characterized in that, comprises the steps:

2. the method for claim 1 is characterized in that: described ordering chained list employing list structure.

3. method as claimed in claim 2, it is characterized in that: described list structure, for each physical block corresponding catena is arranged all, each comprises two pointers, a previous physical block that points to current physical block, another points to a back physical block of current physical block.

4. the method for claim 1 is characterized in that: when the invalid number of pages amount of physical block changes, and immediate updating ordering chained list.

5. the method for claim 1 is characterized in that: after system powers on, need be before carrying out write operation, and described physical block with NOT-AND flash Nandflash sorted by invalid number of pages amount generates the ordering chained list.