Memory system and method for ware leveling

1. A memory system that is connectable to a host,

comprising:

a first memory that is a non-volatile memory;

a controller that associates each of a first number of consecutive logical addresses with each of a first number of physical addresses in a one-to-one manner and updates a correspondence between the first number of consecutive logical addresses and the first number of physical addresses, the first number of physical addresses being included in a second number of consecutive physical addresses of the first memory, the second number being at least one more than the first number; and

a second memory that stores distance information and origin information indicating a physical address associated with a head logical address among the first number of consecutive logical addresses,

wherein a process of updating the correspondence includes:

a first updating of associating a first physical address among the second number of physical addresses with a first logical address of the first number of consecutive logical addresses, and

a second updating of obtaining, after the first updating, a second logical address which is away from the first logical address by a value corresponding to the distance information among the first number of consecutive logical addresses based on the origin information and the distance information and associating a second physical address among the second number of physical addresses with the second logical address, and

the second physical address is a physical address which had been associated with the first logical address before the first updating is executed.

2. The memory system according to claim 1 ,

wherein the process of updating the correspondence includes one or more third updatings,

each of the one or more third updatings is a process of obtaining a third logical address among the first number of consecutive logical addresses based on the origin information and the distance information and associating a third physical address among the second number of physical addresses with the third logical address,

the third logical address is a logical address which is away from a fourth logical address by a value corresponding to the distance information,

the fourth logical address is a logical address which was a target of a previous updating among the first number of consecutive logical addresses, and

the third physical address is a physical address which had been associated with the fourth logical address before the previous updating.

3. The memory system according to claim 2 ,

wherein the controller counts a third number which is a number of times of executed updatings, and

the controller calculates, when specifying an access destination, based on a fifth logical address indicating the access destination and the distance information, a fourth number which is a number of updatings required until the fifth logical address is updated, obtains, when the fourth number is larger than the third number, a fourth physical address associated with the fifth logical address based on the fifth logical address and the origin information, and obtains, when the fourth number is smaller than the third number, the fourth physical address based on the fifth logical address, the origin information, and the distance information.

4. The memory system according to claim 3 ,

wherein the controller obtains a fifth number in each of the third updatings by performing, on the first number, subtraction of the origin information and addition of the distance information for each execution of updating, obtains a first remainder by performing dividing the fifth number by the second number, and obtains the third logical address based on the first remainder, and

the controller obtains a quotient and a second remainder by performing dividing the fifth logical address by the distance information and obtains the fourth number based on the quotient and the second remainder.

5. The memory system according to claim 4 ,

wherein the distance information is a divisor of the first number of consecutive logical addresses.

6. The memory system according to claim 5 ,

wherein each of the distance information and the first number is a power of 2.

7. The memory system according to claim 2 ,

wherein the controller obtains a fifth number by performing subtraction of the origin information and addition of the distance information for each execution of updating on the first number of consecutive logical addresses, obtains a first remainder by performing dividing the fifth number by the second number, and obtains the third logical address based on the first remainder.

8. The memory system according to claim 2 ,

wherein the controller updates the origin information when the updating of the correspondence for all of the first number of consecutive logical addresses is completed.

9. The memory system according to claim 2 ,

wherein the controller determines whether or not the third logical address is invalid, and

the controller migrates, when the third logical address is not invalid, data stored at a location indicated by a fifth physical address to a location indicated by the third physical address, and the fifth physical address is a physical address which had been associated with the third logical address before the third physical address is associated with the third logical address, and

the controller does not perform the migrating of the data when the third logical address is invalid.

10. The memory system according to claim 3 ,

wherein the controller updates the distance information when the updating of the correspondence for all of the first number of consecutive logical addresses is completed.

11. A method of controlling a memory system that is connectable to a host and includes a non-volatile memory, the method comprising:

associating each of a first number of consecutive logical addresses with each of a first number of physical addresses in a one-to-one manner, the first number of physical addresses being included in a second number of consecutive physical addresses of the memory, the second number being at least one more than the first number; and

updating a correspondence between the first number of consecutive logical addresses and the first number of physical addresses, the updating the correspondence including a first updating and a second updating; and

storing distance information and origin information indicating a physical address associated with a head logical address among the first number of consecutive logical addresses,

wherein

the first updating includes associating a first physical address among the second number of physical addresses with a first logical address of the first number of consecutive logical addresses, and

the second updating includes obtaining, after the first updating, based on the origin information and the distance information, a second logical address which is away from the first logical address by a value corresponding to the distance information among the first number of consecutive logical addresses and associating a second physical address among the second number of physical addresses with the second logical address, the second physical address being a physical address which had been associated with the head logical address before the first updating is executed.

12. The method according to claim 11 ,

wherein the updating the correspondence includes one or more third updatings,

each of the one or more third updatings includes obtaining a third logical address among the first number of consecutive logical addresses based on the origin information and the distance information and associating a third physical address among the second number of physical addresses with the third logical address,

the third logical address is a logical address which is away from a fourth logical address by a value corresponding to the distance information,

the fourth logical address is a logical address which was a target of a previous updating among the first number of consecutive logical addresses, and

the third physical address is a physical address which had been associated with the fourth logical address before the previous updating.

13. The method according to claim 12 , further comprising:

counting a third number which is a number of times of executed updatings;

calculating, based on a fifth logical address indicating an access destination and the distance information, a fourth number which is a number of times of updatings required until the fifth logical address is updated;

obtaining, when the fourth number is larger than the third number, a fourth physical address associated with the fifth logical address based on the fifth logical address and the origin information; and

obtaining, when the fourth number is smaller than the third number, the fourth physical address based on the fifth logical address, the origin information, and the distance information.

14. The method according to claim 13 , wherein

each of the third updatings further comprises

obtaining a fifth number by performing, on the first number, subtraction of the origin information and addition of the distance information for each execution of updating, and

obtaining a first remainder by performing dividing the fifth number by the second number, and obtaining the third logical address based on the first remainder, and

the method further comprises

obtaining a quotient by performing dividing the fifth logical address by the distance information and a second remainder and obtaining the fourth number based on the quotient and the second remainder.

15. The method according to claim 14 ,

wherein the distance information is a divisor of the first number of consecutive logical addresses.

16. The method according to claim 15 ,

wherein each of the distance information and the first number is a power of 2.

17. The method according to claim 12 , further comprising:

obtaining a fifth number by performing, on the first number of consecutive logical addresses, subtraction of the origin information and addition of the distance information for each execution of updating;

obtaining a first remainder by performing dividing the fifth number by the second number; and

obtaining the third logical address based on the first remainder.

18. The method according to claim 12 , further comprising,

updating the origin information when the updating of the correspondence for all of the first number of consecutive logical addresses is completed.

19. The method according to claim 12 , further comprising:

determining whether or not the third logical address is invalid;

migrating, when the third logical address is not invalid, data stored at a location indicated by a fifth physical address to a location indicated by the third physical address, the fifth physical address being a physical address which had been associated with the third logical address before the third physical address is associated with the third logical address; and

not performing the migrating of the data when the third logical address is invalid.

20. The method according to claim 13 , further comprising,

updating the distance information when the updating of the correspondence for all of the first number of consecutive logical addresses is completed.