# US 12,007,889 B2 · Valid data identification for garbage collection > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,007,889 B2 - Document ID: US12007889B2 - Status: Granted - Kind: B2 - Application number: 17/968,607 - Filed: 2022-10-18 - Published: 2023-06-15 - Granted: 2024-06-11 - Earliest claimed: 2020-12-21 - Assignees: Micron Technology, Inc. - Applicants: Micron Technology, Inc. - Inventors: David Aaron Palmer - Web page: https://patentgrep.com/patent/US12007889B2 ## CPC - G06F 12/0292: {using tables or multilevel address translation means (G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10)} - G06F 12/0253: {Garbage collection, i.e. reclamation of unreferenced memory} - G06F 12/0891: using clearing, invalidating or resetting means - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Methods, systems, and devices for valid data identification for garbage collection are described. In connection with writing data to a block of memory cells, a memory system may identify a portion of a logical address space that includes a logical address for the data. The memory system may set a bit of a bitmap, which may indicate that the block includes data having a logical address within a portion of the logical address space corresponding to the bit. The logical address space may be divided into any quantity of portions, each corresponding to a different subset of a logical-to-physical (L2P) table, and the bitmap may include any quantity of corresponding bits. To perform garbage collection on the block, the bitmap may be used to identify one or more subsets of the L2P table to evaluate to determine whether different sets of data within the block are valid or invalid. ## Claims ### Claim 1 A non-transitory computer-readable medium storing code comprising instructions which, when executed by a processor of an electronic device, cause the electronic device to: write a set of data to a subset of a block of memory cells of a memory system, the set of data corresponding to a logical address within a logical address space; identify, based at least in part on writing the set of data to the subset of the block of memory cells, a portion of the logical address space that comprises a plurality of logical addresses including the logical address of the set of data; and set a bit of a bitmap based at least in part on the identifying, wherein each bit of the bitmap corresponds to a respective portion of the logical address space, and wherein the bit of the bitmap indicates that data stored within the block of memory cells corresponds to at least one logical address within the respective portion of the logical address space. ### Claim 2 (depends on 1) The non-transitory computer-readable medium of claim 1, wherein the instructions, when executed by the processor of the electronic device, further cause the electronic device to: write a second set of data to a second subset of the block of memory cells, the second set of data corresponding to a second logical address within the logical address space; identify, based at least in part on writing the second set of data to the second subset of the block of memory cells, a second portion of the logical address space that comprises the second logical address; and set a second bit of the bitmap based at least in part on the identifying, wherein the second bit being set indicates that data corresponding to at least one logical address within the second portion of the logical address space is stored within the block of memory cells. ### Claim 3 (depends on 2) The non-transitory computer-readable medium of claim 2, wherein the second portion of the logical address space is discontinuous from the respective portion of the logical address space. ### Claim 4 (depends on 1) The non-transitory computer-readable medium of claim 1, wherein the instructions, when executed by the processor of the electronic device, further cause the electronic device to: write a third set of data to a third subset of the block of memory cells, the third set of data corresponding to a third logical address within the logical address space; identify, based at least in part on writing the third set of data to the third subset of the block of memory cells, that the third logical address is within the respective portion of the logical address space; and ensure, based at least in part on identifying that the third logical address is within the respective portion of the logical address space, that the bit is set. ### Claim 5 (depends on 1) The non-transitory computer-readable medium of claim 1, wherein the instructions, when executed by the processor of the electronic device, further cause the electronic device to: determine, based at least in part on writing the set of data to the block of memory cells, that a threshold quantity of memory cells of the block of memory cells are storing data; and transfer the bitmap from a controller of the memory system to a second subset of the block of memory cells based at least in part on the determining. ### Claim 6 (depends on 1) The non-transitory computer-readable medium of claim 1, wherein the instructions, when executed by the processor of the electronic device, further cause the electronic device to: determine, after setting the bit of the bitmap, to perform a garbage collection operation on the block of memory cells, wherein the block of memory cells stores data corresponding to a plurality of logical addresses within the logical address space; read the bitmap to determine whether one or more logical addresses within the plurality of logical addresses is within the respective portion of the logical address space; evaluate a subset of a logical-to-physical (L2P) table for the logical address space, the subset of the L2P table corresponding to the respective portion of the logical address space, and the evaluating based at least in part on the bit of the bitmap indicating that the at least one logical address within the respective portion of the logical address space is stored within the block of memory cells; identify, based at least in part on the subset of the L2P table, which of the plurality of logical addresses correspond to valid data; and execute the garbage collection operation on the block of memory cells based at least in part on identifying which of the plurality of logical addresses correspond to valid data. ### Claim 7 (depends on 1) The non-transitory computer-readable medium of claim 1, wherein the instructions to set the bit of the bitmap, when executed by the processor of the electronic device, cause the electronic device to: set the bit of the bitmap to a first value, wherein the bit of the bitmap having the first value indicates that the at least one logical address within the respective portion of the logical address space is stored within the block of memory cells, and wherein the bit of the bitmap having a second value indicates that no logical address within the respective portion of the logical address space is stored within the block of memory cells. ### Claim 8 An apparatus, comprising: a memory array; and a controller coupled with the memory array and configured to cause the apparatus to: write a set of data to a subset of a block of memory cells within the memory array, the set of data corresponding to a logical address within a logical address space; identify, based at least in part on writing the set of data to the subset of the block of memory cells, a portion of the logical address space that comprises a plurality of logical addresses including the logical address of the set of data; and set a bit of a bitmap based at least in part on the identifying, wherein each bit of the bitmap corresponds to a respective portion of the logical address space, and wherein the bit of the bitmap indicates that data stored within the block of memory cells corresponds to at least one logical address within the respective portion of the logical address space. ### Claim 9 (depends on 8) The apparatus of claim 8, wherein the controller is further configured to cause the apparatus to: write a second set of data to a second subset of the block of memory cells, the second set of data corresponding to a second logical address within the logical address space; identify, based at least in part on writing the second set of data to the second subset of the block of memory cells, a second portion of the logical address space that comprises the second logical address; and set a second bit of the bitmap based at least in part on the identifying, wherein the second bit being set indicates that data corresponding to at least one logical address within the second portion of the logical address space is stored within the block of memory cells. ### Claim 10 (depends on 9) The apparatus of claim 9, wherein the second portion of the logical address space is discontinuous from the respective portion of the logical address space. ### Claim 11 (depends on 8) The apparatus of claim 8, wherein the controller is further configured to cause the apparatus to: write a third set of data to a third subset of the block of memory cells, the third set of data corresponding to a third logical address within the logical address space; identify, based at least in part on writing the third set of data to the third subset of the block of memory cells, that the third logical address is within the respective portion of the logical address space; and ensure, based at least in part on identifying that the third logical address is within the respective portion of the logical address space, that the bit is set. ### Claim 12 (depends on 8) The apparatus of claim 8, wherein the controller is further configured to cause the apparatus to: determine, based at least in part on writing the set of data to the block of memory cells, that a threshold quantity of memory cells of the block of memory cells are storing data; and transfer the bitmap from memory included in the controller to a second subset of the block of memory cells based at least in part on the determining. ### Claim 13 (depends on 8) The apparatus of claim 8, wherein the controller is further configured to cause the apparatus to: determine, after setting the bit of the bitmap, to perform a garbage collection operation on the block of memory cells, wherein the block of memory cells stores data corresponding to a plurality of logical addresses within the logical address space; read the bitmap to determine whether one or more logical addresses within the plurality of logical addresses is within the respective portion of the logical address space; evaluate a subset of a logical-to-physical (L2P) table for the logical address space, the subset of the L2P table corresponding to the respective portion of the logical address space, and the evaluating based at least in part on the bit of the bitmap indicating that the at least one logical address within the respective portion of the logical address space is stored within the block of memory cells; identify, based at least in part on the subset of the L2P table, which of the plurality of logical addresses correspond to valid data; and execute the garbage collection operation on the block of memory cells based at least in part on identifying which of the plurality of logical addresses correspond to valid data. ### Claim 14 A method, comprising: writing a set of data to a subset of a block of memory cells of a memory system, the set of data corresponding to a logical address within a logical address space; identifying, based at least in part on writing the set of data to the subset of the block of memory cells, a portion of the logical address space that comprises a plurality of logical addresses including the logical address of the set of data; and setting a bit of a bitmap based at least in part on the identifying, wherein each bit of the bitmap corresponds to a respective portion of the logical address space, and wherein the bit of the bitmap indicates that data stored within the block of memory cells corresponds to at least one logical address within the respective portion of the logical address space. ### Claim 15 (depends on 14) The method of claim 14, wherein: write a second set of data to a second subset of the block of memory cells, the second set of data corresponding to a second logical address within the logical address space; identify, based at least in part on writing the second set of data to the second subset of the block of memory cells, a second portion of the logical address space that comprises the second logical address; and set a second bit of the bitmap based at least in part on the identifying, wherein the second bit being set indicates that data corresponding to at least one logical address within the second portion of the logical address space is stored within the block of memory cells. ### Claim 16 (depends on 15) The method of claim 15, wherein the second portion of the logical address space is discontinuous from the respective portion of the logical address space. ### Claim 17 (depends on 14) The method of claim 14, wherein: write a third set of data to a third subset of the block of memory cells, the third set of data corresponding to a third logical address within the logical address space; identify, based at least in part on writing the third set of data to the third subset of the block of memory cells, that the third logical address is within the respective portion of the logical address space; and ensure, based at least in part on identifying that the third logical address is within the respective portion of the logical address space, that the bit is set. ### Claim 18 (depends on 14) The method of claim 14, wherein: determine, based at least in part on writing the set of data to the block of memory cells, that a threshold quantity of memory cells of the block of memory cells are storing data; and transfer the bitmap from a controller of the memory system to a second subset of the block of memory cells based at least in part on the determining. ### Claim 19 (depends on 14) The method of claim 14, wherein: determine, after setting the bit of the bitmap, to perform a garbage collection operation on the block of memory cells, wherein the block of memory cells stores data corresponding to a plurality of logical addresses within the logical address space; read the bitmap to determine whether one or more logical addresses within the plurality of logical addresses is within the respective portion of the logical address space; evaluate a subset of a logical-to-physical (L2P) table for the logical address space, the subset of the L2P table corresponding to the respective portion of the logical address space, and the evaluating based at least in part on the bit of the bitmap indicating that the at least one logical address within the respective portion of the logical address space is stored within the block of memory cells; identify, based at least in part on the subset of the L2P table, which of the plurality of logical addresses correspond to valid data; and execute the garbage collection operation on the block of memory cells based at least in part on identifying which of the plurality of logical addresses correspond to valid data. ### Claim 20 (depends on 14) The method of claim 14, wherein set the bit of the bitmap to a first value, wherein the bit of the bitmap having the first value indicates that the at least one logical address within the respective portion of the logical address space is stored within the block of memory cells, and wherein the bit of the bitmap having a second value indicates that no logical address within the respective portion of the logical address space is stored within the block of memory cells.