METHOD AND APPARATUS FOR MEMORY MANAGEMENT

Abstract

One or more circuits of a device may comprise a memory. A first portion of a first block of the memory may store program code and/or program data, a second portion of the first block may store an index associated with a second block of the memory, and a third portion of the first block may store an indication of a write status of the first portion. Each bit of the third portion of the first block may indicate whether an attempt to write data to a corresponding one or more words of the first portion of the first block has failed since the last erase of the corresponding one or more words of the first portion of the first block. Whether data to be written to a particular virtual address is written to the first block or the second block may depend on the write status of the first block and the second block.

Claims

1. A method comprising: performing by one or more circuits comprising memory, in response to an instruction to write data to said memory: if a first portion of a first block of said memory has been erased more recently than it has been written to, writing data to said first portion of said first block of said memory without first erasing said first block of said memory; if said first portion of said first block of said memory has been written to more recently than it has been erased, and a first portion of a second block of said memory has been erased more recently than it has been written to, writing data to said first portion of said second block of memory without first erasing said second block of said memory; if said first portion of said first block of said memory has been written to more recently than it has been erased, and said first portion of said second block of said memory has been written to more recently than it has been erased, recombining said first block of said memory and said second block of said memory and, subsequent to said recombining, writing said data to said first portion of said first block of said memory.

2. The method of claim 1, wherein said recombining said first block of said memory and said second block of said memory comprises: copying at least some of the contents of said first block of said memory to said second block of said memory; erasing said first block of said memory; and associating an index with said second block of said memory, wherein said index was associated with said first block of said memory prior to said recombining.

3. The method of claim 1, comprising performing by said one or more circuits in response to said instruction to write said data to said memory: converting a virtual memory address of said instruction to an index associated with said first block of said memory.

4. The method of claim 3, comprising performing by said one or more circuits in response to said instruction to write said data to said memory: determining a physical address of said first block of said memory based on said index associated with said first block of said memory.

5. The method of claim 1, comprising performing by said one or more circuits in response to said instruction to write said data to said memory: storing an index associated with a said second block of said memory in said first block of said memory.

6. The method of claim 1, comprising performing by said one or more circuits in response to said instruction to write said data to said memory: reading an index associated with said second block of said memory from said first block of said memory; and determining a physical address of said second block of said memory using said index of said second block of said memory.

7. The method of claim 1, wherein said memory is a NAND flash memory.

8. The method of claim 1, wherein erasing any memory cell of said first block of said memory requires erasing all memory cells of said first block of said memory.

9. The method of claim 1, wherein erasing any memory cell of said second block of said memory requires erasing all memory cells of said second block of said memory.

10. A system comprising: one or more circuits comprising a memory, wherein: a first portion of a first block of said memory stores program code and/or program data; a second portion of said first block of said memory stores an index associated with a second block of said memory; a third portion of said first block of said memory stores an indication of a write status of said first portion of said first one of said memory blocks.

11. The system of claim 10, wherein each bit of said third portion of said first block of said memory indicates whether an attempt to write data to a corresponding one or more words of said first portion of said first block of said memory has failed since the last erase of said corresponding one or more words of said first portion of said first block of said memory.

12. The system of claim 10, wherein: a first portion of said second block of said memory stores program code and/or program data; a second portion of said second block of said memory stores an index associated with said first block of said memory; a third portion of said second block of said memory stores an indication of a write status of said first portion of said second block of said memory.

13. The system of claim 10, wherein said one or more circuits are operable to: receive an instruction to write data to said memory; write said data to a word of said first portion of said first block of said memory if said word of said first portion of said first block of said memory has been erased more recently than it has been written to; and write said data to a word of a first portion of said second block of said memory if said word of said first portion of said first block of said memory has been written to more recently than it has been erased.

14. The system of claim 10, wherein said one or more circuits are operable to: receive an instruction to write data to said memory; detect that (i) a word of said first portion of said first block of said memory has been written to more recently than it has been erased, and (ii) a word of said first portion of said second block of said memory has been written to more recently than it has been erased; and recombine said first block of said memory and said second block of said memory in response to said detection.

15. The system of claim 14, wherein said recombining said first block of said memory and said second block of said memory comprises: copying at least some of the contents of said first block of said memory to said second block of said memory; erasing said first block of said memory; and associating said second block of said memory with an index formerly associated with said first block of said memory.

16. The system of claim 15, wherein said recombining said first block of said memory and said second block of said memory comprises changing an index stored in said second portion of said second block of said memory.

17. The system of claim 16, wherein said index stored in said second portion of said second block of said memory is changed to an index associated with a third block of said memory.

18. The system of claim 16, wherein said index stored in said second portion of said second block of said memory is changed to an index formerly associated with said second block of said memory.

19. The system of claim 16, wherein said new index is randomly selected from a plurality of available indices.

20. The system of claim 10, wherein said memory is a NAND flash memory.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0011] FIG. 1 depicts an exemplary electronic device which manages its memory in accordance with an embodiment of the invention.

[0012] FIG. 2 depicts an exemplary block of memory organized in accordance with an embodiment of the invention.

[0013] FIG. 3 depicts determining a physical address from a virtual address, in accordance with an embodiment of the invention.

[0014] FIG. 4 is a flowchart illustrating exemplary steps for reading from a memory that is managed in accordance with an embodiment of the invention.

[0015] FIG. 5 is a flowchart illustrating exemplary steps for writing to a memory that is managed in accordance with an embodiment of the invention.

[0016] FIG. 6 is a flowchart illustrating exemplary steps for recombining blocks of a memory that is managed in accordance with an embodiment of the invention.

[0017] FIGS. 7A-7G illustrate a series of write operations and a resulting recombination of memory blocks.

[0018] FIGS. 8A-8C illustrate an exemplary recombination of blocks of memory.

DETAILED DESCRIPTION OF THE INVENTION

[0019] As utilized herein the terms circuits and circuitry refer to physical electronic components (i.e. hardware) and any software and/or firmware (code) which may configure the hardware, be executed by the hardware, and or otherwise be associated with the hardware. As utilized herein, and/or means any one or more of the items in the list joined by and/or. As an example, x and/or y means any element of the three-element set {(x), (y), (x, y)}. As another example, x, y, and/or z means any element of the seven-element set {(x), (y), (z), (x, y), (x, z), (y, z), (x, y, z)}. As utilized herein, the terms block and module refer to functions than can be implemented in hardware, software, firmware, or any combination of one or more thereof. As utilized herein, the term exemplary means serving as a non-limiting example, instance, or illustration. As utilized herein, the terms for example and e.g., introduce a list of one or more non-limiting examples, instances, or illustrations.

[0020] FIG. 1 depicts an exemplary electronic device which manages its memory in accordance with an embodiment of the invention. The device 100 comprises a CPU module 102, a power management module 104, an input-output module 106, a clock 108, a random access memory (RAM) module 110, and a memory module 112. In an exemplary embodiment of the invention, the device 100 may be a microcontroller which is realized on a silicon die and integrated in, for example, a smartcard such as is described in the above-incorporated U.S. patent application Ser. No. 13/270,802.

[0021] The CPU 102 may be operable to control operation of the device 100. The CPU 102 may, for example, execute instructions and perform arithmetic and/or logic operations in response to the executed instructions. The CPU 102 may generate one or more control signals for controlling the operation of the device 100.

[0022] The power management module 104 may be operable to condition received power for distribution to various components of the device 100. The power management module 104 may, for example, receive a single voltage (e.g., from a battery) and regulate the voltage to generate a plurality of voltages which may then be distributed to the various components of the device 100.

[0023] The input-output module 106 may be operable to communicate with other devices using one or more proprietary and/or standardized communication protocols (e.g., I.sup.2C, SPI, UART, etc.).

[0024] The clock 108 may be operable to generate one or more oscillating signals which may be utilized to control synchronous circuitry of the device 100. The clock 108 may comprise, for example, one or more crystal oscillators, phase-locked loops, and/or direct digital synthesizers.

[0025] The RAM module 110 may comprise dynamic RAM operable to store runtime data. The memory cells of the RAM module 110 may be volatile such that their contents may be lost relatively-quickly when the RAM module 110 is powered down.

[0026] The memory module 112 may comprise addressing/control logic 118 which implements read and write operations in response to read and write commands issued to the memory module 112. The memory module 112 may comprise nonvolatile memory cells operable to store data that is persistent over multiple power cycles of the device 100. The memory cells may be organized into a look-up table 114 and blocks of memory 116.sub.l-116.sub.M+N. An exemplary memory block 116.sub.X corresponding to one of the blocks 116.sub.l-116.sub.M+N is described below with respect to FIG. 2, for example. An exemplary look-up table 114 is described below with respect to FIG. 3, for example.

[0027] In an exemplary embodiment, the memory module 112 may comprise NAND flash memory which is arranged as described below with respect to FIG. 2, for example. While such an architecture may be efficient in terms of cost and physical area, a drawback of such an architecture is that memory words can only be erased as part of a batch-erase which erases the contents of multiple memory words. For example, erasing any memory word of the block 116.sub.l may require erasing all words of block 116.sub.l.

[0028] In an exemplary embodiment, each of the blocks 116.sub.l-116.sub.M+N may be assigned a unique index and the indices may be utilized for converting a virtual address to a physical address, as described below with respect to FIG. 3, for example. In an exemplary embodiment, one or more of the memory blocks 116.sub.l-116.sub.M+N may be designated as primary blocks and one or more of the memory blocks 116.sub.l-116.sub.M+N may be designated as fallow blocks. The distinction between primary and fallow memory blocks may be utilized to determine which physical address to access when reading from and writing to the memory 112, as is described in further detail below with respect to FIGS. 3-8C, for example.

[0029] In operation, the CPU 100 may execute program code that is stored in the memory 112 causing the device 100 to operate in accordance with the code. Execution of the program code causes reading of program code and/or data (e.g., parameters utilized during execution of the program code) from the memory module 112. An exemplary manner in which such read operations are carried out is described below with respect to FIG. 4, for example. Reading of program code and/or data from memory 112 of course requires the code and/or data to have been written to the memory 112 in the first place. An exemplary manner in which program data and/or code may be written to the memory 112 is described below with respect to FIGS. 5 and 7A-7G, for example. Such write operations may be carried out, for example, in response to instructions from a programming station connected via I/O module 106. Such write operations may also be carried out, for example, in response to instructions from the CPU 102 during runtime when program data needs to be updated and/or when the module 112 is utilized for runtime data (e.g., due to RAM 110 being full).

[0030] FIG. 2 depicts an exemplary block of memory organized in accordance with an embodiment of the invention. The block of memory 116.sub.X shown in FIG. 2 comprises a first portion 202, a second portion 206, and a third portion 208. In an exemplary embodiment, each of the blocks 116.sub.l-116.sub.M+N may be organized like the block 116.sub.X.

[0031] The first portion 202 of the memory block 116.sub.X comprises one or more memory cells operable to store one or more words of information, where each word may be one or more bits in length. In an exemplary embodiment, program code and/or program data may be stored in first portion 202.

[0032] The second portion 206 of the memory block 116.sub.X comprises one or more memory cells operable to store one or more words of information. In an exemplary embodiment, the second portion 206 of the memory block 116.sub.X may comprise a field 210 which may store an index associated with one of the memory blocks 116.sub.l-116.sub.M+N that has been designated as a primary block. In an exemplary embodiment, the second portion 206 of the memory block 116x may comprise a field 212 which may store an index associated with one of the memory blocks 116.sub.l-116.sub.M+N that has been designated as a fallow block. In this regard, a primary memory block may be associated with a fallow block by storing the index of the fallow memory block in field 212 of the primary block and storing the index of the primary block in field 210 of the fallow block. For example, if the block 116.sub.X has been designated as a primary memory block, then the index stored in field 210 may be the index associated with the block 116.sub.X and the index stored in field 212 may be the index of a block 116.sub.Y that has been designated as a fallow block. Conversely, if the block 116.sub.X has been designated as a fallow block, then the index stored in field 212 may be the index associated with the block 116.sub.X and the index stored in field 210 may be the index of a block 116.sub.Y that has been designated as a primary block. In an exemplary embodiment, a value in field 212 that is beyond the range of valid indices may indicate that the block 116.sub.X is not a fallow block and has not been associated with the block 116.sub.X.

[0033] The third portion 208 of the memory block 116.sub.X comprises one or more memory cells operable to store indications of whether an attempt to write data to the portion 202 has failed since the last time the portion 202 has been erased. A write attempt may fail, for example, because the portion 202 has been written to more recently than it has been erased. Such write failures arise from, for example, the limitations of NAND flash architecture that allows only per-block erase (and not erasure of individual words of a block). In an exemplary embodiment, each bit of the third portion 208 may indicate whether a corresponding one or more words of the first portion 202 have had a write failure since the last erase of the block 116.sub.X. Those words of the portion 202 for which the corresponding bit(s) of the portion 208 are asserted (that is, those memory cells of the portion 202 that have had a write failure since the last erase of the block 116.sub.X) may be said to be closed. Those words of the portion 202 for which the corresponding bit(s) of the portion 208 are deasserted (that is, those memory cells of the portion 202 that have not had a write failure since the last erase of the block 116.sub.X) may be said to be open.

[0034] FIG. 3 depicts determining a physical address from a virtual address, in accordance with an embodiment of the invention. Shown in FIG. 3, a virtual address 302 comprises a first portion 304 and a second portion 306. The first portion 304 may determine which one of the blocks 116.sub.l-116.sub.M+N is to be read from or written to, and the portion 306 of the virtual address may determine which word(s) within the block is/are to be read from or written to. For example, in the embodiment shown in FIG. 3, each block comprises W words, the portion 304 of the virtual address 302 maps to block 116.sub.j, and the portion 306 of the virtual address 302 corresponds to an address offset of w words, where word size in the memory module 112 may be one or more bits, and the address offset may be counted in units of single words or multiple words (e.g., for batch read/write).

[0035] In instances that a fallow block has been associated with a primary block, the fallow block may be read from or written to by first reading the index of the fallow block from the primary block, mapping the index to the physical address of the fallow block using table 114, and then using the portion 306 of the virtual address 302 to determine an address offset within the fallow block. For example, in the embodiment shown in FIG. 3, index n is stored in field 212 of block 116.sub.j, index n maps to block 116k in table 114, and the portion 306 of virtual address 302 corresponds to an address offset of w words.

[0036] FIG. 4 is a flowchart illustrating exemplary steps for reading from a memory that is managed in accordance with an embodiment of the invention. The exemplary steps begin with step 402 in which an instruction to read from a particular virtual address is input to the memory 402.

[0037] In step 404, the index of the primary block to be read from, and the address offset of the word(s) to be read, are determined from the virtual address. For example, the index may be determined from a first portion of the virtual address and the address offset may be determined from a second portion of the virtual address. For non-limiting illustration purposes only, the remainder of the description of FIG. 4 assumes the result of step 404 is a determination that the index of the primary block is m and that the address offset is w.

[0038] In step 406, the index determined in step 404 is used to determine a corresponding physical address of the primary block. For example, the index m is input to the look-up table 114 and the physical address of the primary block 116.sub.j is output by the look-up table.

[0039] In step 408, it is determined whether a fallow block has been associated with the primary block 116.sub.j. For example, if the value of the field 212 of the block 116.sub.j is above a threshold, it may be determined that no fallow block has been associated with the block 116.sub.j, but if the value of the field 212 of the block 116.sub.j is below the threshold, it may be determined that a fallow block has been associated with the block 116.sub.j. If there is no associated fallow block, the exemplary steps may proceed to step 416. In step 416, the word or words at address offset w of block 116.sub.j are read and output from the memory module 112.

[0040] Returning to step 408, if there is an associated fallow block, then the exemplary steps may proceed to step 410. In step 410, it is determined whether the word or words at address offset w of block 116.sub.j are open (i.e., have not had a write failure since the last erase of the block 116.sub.j). If the word(s) are open, then the exemplary steps may proceed to step 416.

[0041] Returning to step 410, if the word or words at address offset w of block 116.sub.j are closed, then the exemplary steps may proceed to step 412. In step 412, the physical address of the associated fallow block may be determined. The physical address of the fallow block may be determined by reading the index from field 212 of the block 116.sub.j, and using the index to determine the physical address (e.g., via a look-up table) of the fallow block. For non-limiting illustration purposes only, it is assumed in step 414 that block 116k has been designated as a fallow block and associated with the block 116.sub.j. Subsequent to step 412, the exemplary steps may proceed to step 414. In step 414, the word(s) at address offset w of block 116k are read and output from the memory module 112.

[0042] FIG. 5 is a flowchart illustrating exemplary steps for writing to a memory that is managed in accordance with an embodiment of the invention. The exemplary steps begin with step 502 in which an instruction to write data to a virtual address is input to the memory 402.

[0043] In step 504, the index of the primary block to be written to, and the address offset of the word or words to be written to, are determined from the virtual address. For example, the index may be determined from a first portion of the virtual address and the address offset may be determined from a second portion of the virtual address. For non-limiting illustration purposes only, the remainder of the description of FIG. 5 assumes the result of step 504 is a determination that the primary block to be written to is block 116.sub.j, and that the word(s) to be written to are at address offset w.

[0044] In step 505, the variable ADRS is set to the physical address of the word(s) having an address offset w in block 116.sub.j. Also in step 505, the variable C is set to 0.

[0045] In step 506, it is determined whether the word(s) located at the physical address ADRS are open (i.e., have not had a write failure since the last erase of the block 116.sub.j). If so, then the exemplary steps proceed to step 508.

[0046] In step 508, an attempt is made to write the data received in step 502 to the word(s) having the physical address ADRS. If the write is successful, then the exemplary steps proceed to step 528 and the write operation is complete.

[0047] Returning to step 508, if the write operation is unsuccessful (e.g., because the memory cells at ADRS have already been written to since the last erase of block 116.sub.j), then the exemplary steps may proceed to step 510. In step 510, the word(s) at address offset w of block 116.sub.j may be marked as closed (e.g., by asserting a corresponding one or more bits of the portion 208 of the block 116.sub.j).

[0048] In step 512, the value of C determines which of the exemplary steps is next. If C=0 or 2, then the exemplary steps proceed to step 514. In step 514, it is determined whether a fallow block has been associated with the primary block 116.sub.j. For example, if the value of the field 212 of the block 116.sub.j is above a threshold, it may be determined that no fallow block has been associated with the block 116.sub.j, but if the value of the field 212 of the block 116.sub.j is below the threshold, it may be determined that a fallow block has been associated with the block 116.sub.j. If there is an associated fallow block, the exemplary steps may proceed to step 522. For non-limiting illustration purposes only, step 522 assumes that block 116.sub.k is a fallow block associated with primary block 116.sub.j. Accordingly, in step 522, the variable ADRS is set to the physical address of the word or words at address offset w in block 116.sub.k. After step 522, the exemplary steps proceed to step 530 in which the variable C is incremented by one.

[0049] Returning to step 514, if there is no fallow block associated with block 116j, then the exemplary steps may proceed to step 516. In step 516 it is determined whether there is a block available to be associated with the block 116.sub.j. That is, it is determined whether any of the blocks 116.sub.l-116.sub.M+N is not currently associated with a primary block and is not currently being utilized as a primary block. In instances that there is an available block, the exemplary steps may proceed to step 520. In step 520 an available block may be associated with the block 116.sub.j. Assuming, for illustration, that block 116.sub.k is available, in step 516, block 116.sub.k may be associated with the block 116.sub.j. The association may comprise: (1) assigning an index to the block 116.sub.k; and (2) storing the index of block 116.sub.k in field 212 of the block 116.sub.j.

[0050] Returning to step 516, if none of the blocks 116.sub.l-116.sub.M+N is available to be associated with the block 116.sub.j, the exemplary steps may proceed to step 518. In step 518, a primary block other than block 116.sub.j may be recombined with its associated fallow block. Which block is selected for recombining may, for example, be selected randomly and/or according to an algorithm that achieves wear-leveling of the memory module 112. Exemplary steps for recombining a primary block with its associated fallow block are described below with respect to FIG. 6, for example.

[0051] Returning to step 512, if C=1, then the exemplary steps may advance to step 524. In step 524, the block 116.sub.j may be recombined with its associated fallow block. Exemplary steps for recombining a primary block with its associated fallow block are described below with respect to FIG. 6, for example.

[0052] Returning to step 512, if C=3 then the exemplary steps may advance to step 526. In this regard, the variable C reaching a value of three may indicate that there is file system fault (e.g., due to running out of memory in the module 112). In step 526, a fault indication may be generated and conveyed to the CPU 102 and/or output via the I/O module 106.

[0053] FIG. 6 is a flowchart illustrating exemplary steps for recombining blocks of a memory that is managed in accordance with an embodiment of the invention. The exemplary steps begin with step 602 in which an index of a primary block to be recombined is determined. The index of the block to be recombined may, for example, be determined using a wear-leveling algorithm or based on the target address of a write operation.

[0054] In step 604, it is determined whether a fallow block has been associated with the primary block. For example, if the value of the field 212 of the primary block is above a threshold, it may be determined that no fallow block has been associated with the primary block, but if the value of the field 212 of the primary block is below the threshold, it may be determined that a fallow block has been associated with the primary block. If there is no associated fallow block to recombine with the primary block, then the exemplary steps proceed to step 616. If there is an associated fallow block, then the exemplary steps may proceed to step 606.

[0055] In step 606, a counter z is initialized to 0. In step 608, z is compared to B, which is the number of words in the portion 202 of the primary block. If z is less than B, then the exemplary steps proceed to step 610. In step 610, it is determined whether the word or words at address offset z in the primary block are open (i.e., whether there has been a failed write attempt to the word(s) since the last erase of the primary block). If the word(s) are open, then the exemplary steps may advance to step 612. In step 612, the contents of the word(s) at address offset z in the primary block may be copied to the word(s) at address offset z in the associated fallow block.

[0056] Returning to step 610, if the word(s) at address offset z in the primary block are closed, then the exemplary steps may advance to step 614. That is, closed words are not copied to the associated fallow block. In step 614, z is incremented by 1.

[0057] Returning to step 608, if z is greater than or equal to B, then the exemplary steps may proceed to step 618. In step 618, the contents of the primary block may be erased. In a NAND flash architecture this may result in all memory cells of the block being set to 1. In step 620, the index fields 210 and/or 212 of the primary block and the fallow block may be updated. In an exemplary embodiment, the field 210 of the primary block may be swapped with the field 210 of the fallow block, and the field 212 of the primary block may be swapped with the field 212 of the fallow block. In step 622, the recombination is complete.

[0058] FIGS. 7A-7G illustrate a series of write operations and a resulting recombination of memory blocks. FIGS. 7A-7G depict two exemplary blocks 116.sub.j and 116.sub.k and a portion of the table 114. Each of the blocks 116.sub.j and 116.sub.k has four 8-bit words with address offsets of 0, 1, 2, and 3, respectively.

[0059] In FIG. 7A, the block 116.sub.j is designated as a primary block and the block 116k is designated as a fallow block, index i1 is associated with block 116.sub.j, index i4 is associated with block 116.sub.k, and blocks 116.sub.j and 116.sub.k are associated with each other (as indicated by block 116.sub.j storing index i4 and block 116.sub.k storing index i1). FIG. 7A depicts the two blocks in a condition where neither block has been written to since it was last erased.

[0060] FIG. 7B depicts the blocks 116.sub.j and 116.sub.k after a batch write has caused each of words 0-3 of the block 116.sub.j to be written to. That is, FIG. 7B depicts the blocks 116.sub.j and 116.sub.k after execution of an instruction to write words of data to a particular virtual address which resolved to an address offset of 0 of block 116.sub.j.

[0061] FIG. 7C depicts the blocks 116.sub.j and 116.sub.k after execution of a second write to the same virtual address. Because the word at address offset 1 of block 116.sub.j had already been written to, however, the write to block 116.sub.j failed. As a result, word 1 of block 116.sub.j was marked as closed by asserting bit f1 of block 116.sub.j and the data was written to the word 1 of the associated fallow block 116.sub.k.

[0062] FIG. 7D depicts the blocks 116.sub.j and 116.sub.k after a first stage of a recombination of blocks 116.sub.j and 116.sub.k. The recombination may have been triggered by, for example, a third write instruction targeting the same virtual address (the write is completed in FIG. 7G below). In FIG. 7D, data stored in the open words of block 116.sub.j have been copied to the corresponding words of block 116.sub.k.

[0063] FIG. 7E depicts the blocks 116.sub.j and 116.sub.k after a second stage of a recombination of blocks 116.sub.j and 116.sub.k. In FIG. 7E, block 116.sub.j has been erased.

[0064] FIG. 7F depicts the blocks 116.sub.j and 116.sub.k after a third stage of a recombination of blocks 116.sub.j and 116.sub.k. In FIG. 7F, index i1 has been disassociated from block 116.sub.k and associated with block 116.sub.j. Additionally, the contents of the field 212 of block 116.sub.j have been swapped with the contents of the field 212 of the block 116.sub.k. Thus, in FIG. 7F, block 116.sub.k has become a primary block and block 116.sub.j has become a fallow block associated with the primary block 116.sub.k.

[0065] FIG. 7G depicts the blocks 116.sub.j and 116.sub.k after a third write to the same virtual address. Because word 1 of the primary block 116.sub.k had already been written to, the write to block 116.sub.k failed. As a result, word 1 of block 116.sub.k was marked as closed by assertion of bit fl of block 116.sub.k and the data was written to the word 1 of the associated fallow block 116.sub.j.

[0066] FIGS. 8A-8C illustrate an exemplary recombination of blocks of memory. The recombination depicted in FIGS. 8A-8C differs from the recombination shown in FIGS. 7D-7F in that rather than swapping primary and fallow blocks, the fallow block becomes the primary block, a new fallow block is designated and associated with the primary block, and the old fallow block becomes available.

[0067] FIG. 8A depicts the blocks 116.sub.j, 116.sub.k and 116.sub.l after a first stage of a recombination of blocks 116.sub.j and 116.sub.k, where block 116.sub.j is a primary block and block 118.sub.k is a fallow block associated with block 116.sub.j In FIG. 8A, data stored in the open words of block 116.sub.j have been copied to the corresponding words of block 116.sub.k.

[0068] FIG. 8B depicts the blocks 116.sub.j, 116.sub.k, and 116.sub.l after a second stage of a recombination of blocks 116.sub.j and 116.sub.k. Specifically, block 116.sub.j has been erased.

[0069] FIG. 8C depicts the blocks 116.sub.j, 116.sub.k, and 116.sub.l after a third stage of a recombination of blocks 116.sub.j and 116.sub.k. In FIG. 8C, index i1 has been disassociated from block 116.sub.k and associated with block 116.sub.j, and index i4 has been disassociated with block 116.sub.j and associated with block 116.sub.l. Additionally, the index formerly in field 212 of block 116.sub.j has been copied to field 212 of the block 116.sub.k, and the index i1, now associated with block 116.sub.k, has been stored to field 212 of block 116.sub.l. Thus, in FIG. 8C, block 116.sub.k has become a primary block, block 116.sub.l has become a fallow block associated with the primary block 116.sub.k, and block 116.sub.j is available to be used as a primary block or as a fallow block. Block 116.sub.l may have been selected as a fallow block for block 116.sub.k based, for example, on a wear-leveling algorithm.

[0070] In an exemplary embodiment, an instruction to write data to a particular virtual address of memory 212 may result in the device 100 writing data to a first portion, word 1, of a primary block, block 116.sub.j, or to a first portion, word 1, of a fallow block 116.sub.k. If word 1 of block 116.sub.j has been erased more recently than it has been written to, the data may be written to word 1 of block 116.sub.j, without first erasing block 116.sub.j. If word 1 of block 116.sub.j has been written to more recently than it has been erased, and word 1 of block 116.sub.k has been erased more recently than it has been written to, the data may be written to word 1 of block 116.sub.k without first erasing the second block of the memory. If word 1 of block 116.sub.j has been written to more recently than it has been erased, and word 1 of block 116.sub.k has been written to more recently than it has been erased, block 116j and 116k may be recombined, and, subsequent to the recombining, the data may be written to word 1 of block 116.sub.j. The recombining of blocks 116.sub.j and 116.sub.k may comprise copying at least some of the contents of block 116.sub.j to block 116.sub.k, erasing block 116.sub.j, and associating, with block 116.sub.k, an index that, prior to the recombining, was associated with block 116.sub.j.

[0071] In executing the write instruction, the device 100 may convert the virtual address to an index associated with block 116.sub.j. In executing the write instruction, the device 100 may determine a physical address block 116.sub.j based on the index associated with block 116.sub.j. In executing the write instruction, the device 100 may store an index associated with block 116.sub.k in field 212 of block 116.sub.j. In executing the write instruction, the device 100 may read an index associated with block 116.sub.k from field 212 of block 116j, and determine a physical address of block 116.sub.k using the index.

[0072] In an exemplary embodiment, one or more circuits of a device 100 may comprise a memory 112, where a first portion 202 of a first block 116.sub.j of the memory 112 may store program code and/or program data, a second portion 206 of the first block 116.sub.j may store an index associated with a second block 116.sub.k of the memory 112, and a third portion 208 of the first block 116.sub.j may store an indication of a write status of the first portion 208. Each bit of the third portion 208 may indicate whether an attempt to write data to a corresponding one or more words of the first portion 202 of the first block 116.sub.j has failed since the last erase of the corresponding one or more words of the first portion 202 of the first block 116.sub.j. Regarding the second block 116.sub.k, a first portion 202 of the second block 116.sub.k may store program code and/or program data, a second portion 206 of the second block 116.sub.k may store an index associated with the first block 116.sub.j, and a third portion of the second block 116.sub.k may store an indication of a write status of the first portion 202 of the second block 116.sub.k.

[0073] The one or more circuits of the device 100 may be operable to receive an instruction to write data to the memory 112. In response to the received instruction, the one or more circuits may write the data to a word of the first portion 202 of the first block 116.sub.j if the word of the first portion 202 of the first block 116.sub.j has been erased more recently than it has been written to, and write the data to a word of the first portion 202 of the second block 116.sub.k if the word of the first portion 202 of the first block 116.sub.j has been written to more recently than it has been erased. Additionally or alternatively, in response to the received write instruction, the one or more circuits may detect that (i) a word of the first portion 202 of the first block 116.sub.j has been written to more recently than it has been erased, and (ii) a word of the first portion 202 of the second block 116.sub.k has been written to more recently than it has been erased. In response to the detection, the one or more circuits may recombine the first block 116.sub.j and the second block 116.sub.k in response to the detection. The recombining may comprise copying at least some of the contents of the first block 116.sub.j to the second block 116.sub.k, erasing the first block 116.sub.j, and associating the second block 116.sub.k with an index formerly associated with the first block 116.sub.k. The recombining may also comprises changing an index stored in the second portion 206 of the second block 116.sub.k. The index stored in the second portion 206 of the second block 116.sub.k may be changed to an index that is associated with a third block 116.sub.l (e.g., index i4 in FIG. 8C) and/or that was former formerly associated with the second block 116.sub.k (e.g., index i4 in FIG. 7G).

[0074] Other embodiments of the invention may provide a non-transitory computer readable medium and/or storage medium, and/or a non-transitory machine readable medium and/or storage medium, having stored thereon, a machine code and/or a computer program having at least one code section executable by a machine and/or a computer, thereby causing the machine and/or computer to perform the steps as described herein for memory management.

[0075] Accordingly, the present invention may be realized in hardware, software, or a combination of hardware and software. The present invention may be realized in a centralized fashion in at least one computing system, or in a distributed fashion where different elements are spread across several interconnected computing systems. Any kind of computing system or other apparatus adapted for carrying out the methods described herein is suited. A typical combination of hardware and software may be a general-purpose computing system with a program or other code that, when being loaded and executed, controls the computing system such that it carries out the methods described herein. Another typical implementation may comprise an application specific integrated circuit or chip.

[0076] The present invention may also be embedded in a computer program product, which comprises all the features enabling the implementation of the methods described herein, and which when loaded in a computer system is able to carry out these methods. Computer program in the present context means any expression, in any language, code or notation, of a set of instructions intended to cause a system having an information processing capability to perform a particular function either directly or after either or both of the following: a) conversion to another language, code or notation; b) reproduction in a different material form.

[0077] While the present invention has been described with reference to certain embodiments, it will be understood by those skilled in the art that various changes may be made and equivalents may be substituted without departing from the scope of the present invention. In addition, many modifications may be made to adapt a particular situation or material to the teachings of the present invention without departing from its scope. Therefore, it is intended that the present invention not be limited to the particular embodiment disclosed, but that the present invention will include all embodiments falling within the scope of the appended claims.