Overlaid erase block mapping
View Patent ↗An overlaid erase block (EB) mapping scheme for a flash memory provides efficient wear-leveling and reduces mount operation latency. The overlaid EB mapping scheme maps a first type of EB onto one of a plurality of physical erase blocks, in a corresponding portion of the flash memory. The first type of EB includes a plurality of pointers. The overlaid EB mapping scheme also maps each of second and third types of EBs onto one of the physical EBs that is not mapped to the first type of EB. The second type of EBs store system management information and the third type of EBs store user data. When the flash memory is started up, the overlaid EB mapping scheme scans the corresponding portion to locate the first type of EB, locates the system EBs using the pointers, and locates the data EBs using the system management information.
1. A method comprising:
mapping a first type of erase block (EB), which includes a plurality of pointers, onto one of first physical EBs, of a plurality of physical EBs in a memory;
mapping each of second type of EBs and third type of EBs onto at least one of the first physical EBs and second physical EBs of the plurality of physical EBs that is not mapped to the first type of EB, the second type of EBs storing system management information and the third type of EBs storing user data;
when the memory is started up, locating the first type of EB through scanning the first physical EBs and without scanning the second physical EBs; and
reclaiming the first type of EB using one of a fourth type of EBs, wherein the one of the fourth type of EBs is within the first physical EBs.
2. The method of claim 1 , further comprising, when the memory is started up:
locating the second type of EBs using the pointers; and
locating the third type of EBs using the system management information.
3. The method of claim 1 , further comprising:
mapping the fourth type of EBs onto the physical EBs;
wherein each of the fourth type of EBs is an empty physical EB used for reclaiming one of the first type of EB, the second type of EBs and the third type of EBs.
4. The method of claim 3 , further comprising, in response to the first type of EB being full and one or more of the fourth type of EBs being mapped within the first physical EBs:
allocating the one of the fourth type of EBs mapped within the first physical EBs to reclaim the first type of EB.
5. The method of claim 3 , further comprising, in response to the first type of EB being full, no fourth type of EB being mapped within the first physical EBs and one or more second type of EBs being mapped within the first physical EBs:
generating one or more of the fourth type of EBs within the first physical EBs by allocating one or more of the fourth type of EBs outside of the first physical EBs to reclaim one or more of the second type of EBs within the first physical EBs; and
allocating the one of the fourth type of EBs generated within the first physical EBs to reclaim the first type of EB.
6. The method of claim 3 , further comprising, in response to the first type of EB being full and no fourth type of EB and no second type of EB being mapped within the first physical EBs:
generating one or more of the fourth type of EBs within the first physical EBs by allocating one or more of the fourth type of EBs outside of the first physical EBs to reclaim one or more of the third type of EBs within the first physical EBs; and
allocating the one of the fourth type of EBs generated within the first physical EBs to reclaim the first type of EB.
7. A system, comprising:
a memory including a plurality of physical EBs, the plurality of physical EBs including a first plurality of physical EBs and a second plurality of physical EBs; and
one or more data processing devices configured to:
map a first type of EB, which includes pointers, onto one of the second plurality of physical EBs,
map each of second and third types of EBs onto one of the the first plurality of physical EBs or the second plurality of physical EBs that is not mapped to the first type of EB, wherein the second type of EBs store system management information, and the third type of EBs store user data;
locate the first type of EB through a scan of the second plurality of physical EBs, without a scan of the first plurality of physical EBs, when the memory is started up; and
reclaim the first type of EB using one of a fourth type of EBs, wherein the one of the fourth type of EBs is within the second plurality of physical EBs.
8. The system of claim 7 , the one or more data processing devices further configured to, when the memory is started up:
locate the second type of EBs using the pointers; and
locate the third type of EBs using the system management information.
9. The system of claim 7 , the one or more data processing devices further configured to:
map the fourth type of EBs onto the physical EBs, wherein each of the fourth type of EBs is an empty physical EB used for reclaiming one of the first type of EB, the second type of EBs and the third type of EBs.
10. The system of claim 9 , the one or more data processing devices further configured to, in response to the first type of EB being full and one or more fourth type of EBs being mapped within the second plurality of physical EBs:
allocate the one of the fourth type of EBs mapped within the second plurality of physical EBs to reclaim the first type of EB.
11. The system of claim 9 , the one or more data processing devices further configured to, in response to the first type of EB being full, no fourth type of EB being mapped within the second plurality of physical EBs and one or more second type of EBs being mapped within the second plurality of physical EBs:
generate one or more of the fourth type of EBs within the second plurality of physical EBs by allocating one or more of the fourth type of EBs outside of the second plurality of physical EBs to reclaim one or more of the second type of EBs within the second plurality of physical EBs; and
allocate the one of the fourth type of EBs generated within the second plurality of physical EBs to reclaim the first type of EB.
12. The system of claim 9 , the one or more data processing devices further configured to, in response to the first type of EB being full and no fourth type of EB and no second type of EB being mapped within the second plurality of physical EBs:
generate one or more of the fourth type of EBs within the second plurality of physical EBs by allocating one or more of the fourth type of EBs outside of the second plurality of physical EBs to reclaim one or more of the third type of EBs within the second plurality of physical EBs; and
allocate the one of the fourth type of EBs generated within the second plurality of physical EBs to reclaim the first type of EB.
13. A tangible computer-readable device including a plurality of physical EBs and having instructions stored thereon that, when executed by at least one computing device, causes the at least one computing device to perform EB mapping operations comprising:
mapping a first type of EB, which includes pointers, onto one of first physical EBs of the plurality of physical EBs of the tangible computer-readable device;
mapping each of second and third types of EBs onto one of the first physical EBs or to one of second physical EBs of the plurality of physical EBs that is not mapped to the first type of EB, wherein the second type of EBs store system management information, and the third type of EBs store user data;
mapping a fourth type of EBs respectively onto the physical EBs, wherein each of the fourth type of EBs is an empty physical EB used for reclaiming one of the first type of EBs, the third type of EBs and the second type of EBs;
scanning within the first physical EBs, to locate the first type of EB without scanning the second physical EBs, when the computer-readable device is started up; and
reclaiming the first type of EB using one of the fourth type of EBs, wherein the one of the fourth type of EBs is within the first physical EBs of the computer-readable device.
14. The computer-readable device of claim 13 , the EB mapping operations further comprising, when the computer-readable device is started up:
locating the second type of EBs using the pointers; and
locating the third type of EBs using the system management information.
15. The computer-readable device of claim 13 , the EB mapping operations further comprising, in response to the first type of EB being full and one or more fourth type of EBs being mapped within the first physical EBs:
allocating the one of the fourth type of EBs mapped within the corresponding portion to reclaim the first type of EB.
16. The computer-readable device of claim 13 , the EB mapping operations further comprising, in response to the first type of EB being full, no fourth type of EB being mapped within the first physical EBs and one or more second type of EBs being mapped within the first physical EBs:
generating one or more of the fourth type of EBs within the first physical EBs by allocating one or more of the fourth type of EBs outside of the first physical EBs to reclaim one or more of the second type of EBs within the first physical EBs; and
allocating the one of the fourth type of EBs generated within the first physical EBs to reclaim the first type of EB.
17. The computer-readable device of claim 13 , the EB mapping operations further comprising, in response to the first type of EB being full and no fourth type of EB and no second type of EB being mapped within the first physical EBs:
generating one or more of the fourth type of EBs within the first physical EBs by allocating one or more of the fourth type of EBs outside of the first physical EBs to reclaim one or more of the third type of EBs within the first physical EBs; and
allocating the one of the fourth type of EBs generated within the first physical EBs to reclaim the first type of EB.