As noted by pjc50, the general concept is that one avoids having a fixed relationship between logical addresses and physical addresses. Each time a request is made to write a page, simply use another page that's known to be blank, and make a note that the block is now stored at the new location.
Conceptually, this is nice and easy. Depending upon how many independently-mapped pages you have to deal with, it might be relatively easy in practice too (particularly if the number of mapped pages is small enough that you can afford to keep the entire table of actual page locations in RAM, and can afford the time to scan for all live pages and note their locations in the table). If the number of pages is large, however, it may be necessary to keep some tables in the flash which are organized in such fashion as to quickly find the particular physical block associated with a logical address. Trying to the hold locations of all the 512-byte pages in a 32GB flash, for example, would require about 256MB of memory, and even if one could process a million pages per second, loading that memory would take over a minute.
One could, in theory, have pages that hold the locations of 128 other pages, have pages that hold the location of 128 of those (indirectly holding the location of 16,384 pages), have pages that hold 128 of those (2,097,152 pages), and have a page that holds about 32 of those (which would manage 67,108,864 pages of data). To find a page page N, use bits 21-25 of the page number to select one of 32 page addresses in that last-mentioned page, then bits 14-20 to select one of 128 page addresses in that one, then bits 7-14 to select one of the 128 page addresses in that one, and finally bits 0-6 to select a page in that one. Voila--one now has the address of the page one needs.
Unfortunately, this approach means that reading each page of memory requires reading five pages from the flash chip, and even worse--writing each page of memory will require rewriting the page that holds its address, which will in turn require rewriting the page that holds that page's address, which will in turn require rewriting the page that holds that page's address, etc. Five pages total. Ick.
One may improve things considerably if one allows for the possibility that the data in the page maps need not be kept absolutely current if, every time a page gets replaced, the address of the new page is written in a previously-blank spot in the tag memory of the old page. Such allowance may degrade read performance since a pointer that's supposed to go to a page may point to an old version, which may point to another old version, etc. before finally reaching the right page. On the other hand, such an allowance may enormously improve write performance.
For example, even if one only allows a single extra level of redirection (meaning that if a page has been moved once without updating the parent pointer, the parent pointer must be updated on the next move), half the writes to a page would only require writing a page plus a tag, a quarter would require writing two pages plus a tag, an eight would require three pages plus a tag, etc. A pretty big improvement compared with every addressed page-write requiring that six pages get rewritten. If one allows up to three extra levels of indirection (every fourth write at a given level requires a parent update), then 3/4 of updates will be one write plus a tag, 3/16 will be two, 3/64 will be three, and only 1/64 will require more than that.
Note that while allowing multiple levels of redirection may slow down read performance, this may be more than offset by caching in RAM the addresses of recently-used blocks. If the contents of a cache entry are lost (whether because power was removed, or because it "expired") the next access to its page will be slower than usual, but use of tags for the updates would mean that correct data would still be found.
Designing good algorithms to manage a flash device is tricky. Although Micron seems to suggest having the entire chip be a unified "zone", I don't think that's quite practical. At minimum, there must be a means of locating the master indexing page. My recommendation would be that at any given time, the master indexing page be confined to one of a fairly small number of blocks. The locations of those blocks should be kept in one of a few super-master blocks which are devoted to that purpose. Every few hundred times the master indexing page has cycled through its allocated blocks, a new set of blocks should be chosen for it and the super-master blocks updated to reflect that. The number of super-master blocks would be small enough that the system could examine all of them on startup, and the number of master blocks listed in the active super-master block would be small enough that the system could examine all of those. Since there could be thousands of changes to the master block for each each to the super-master block, there should be no problem with the latter wearing out.
