Page validity bitmap
A page validity bitmap is per-physical-page FTL metadata used to identify data that must be retained when reclaiming a flash block.
Validity concerns whether stored data remains logically current, not whether its bytes pass a checksum. An overwritten page can become invalid without being erased. Address translation locates a logical page; validity tracking helps garbage collection decide which physical pages still need preservation. [1]
Bit meaning: In the Gecko papers, 1 marks an invalid page. Erasing a block clears its bits because its pages become free, not because they contain live data. A zero bit alone is therefore not proof of a programmed, current page. Interpret the bitmap with its allocation state and update rules. [1]
Delayed updates: In the 2015 Lazy Gecko design, an overwrite may not know the previous physical address when its mapping is absent from cache. Translation-page reads resolve delayed invalidations; reverse-map and cached-state checks reconcile remaining obsolete pages before migration. Lazy Gecko is the paper's garbage collector, not LazyFTL. [2]
A flat one-bit-per-page bitmap needs ceil(N/8) payload bytes for N physical pages, before alignment or indexing overhead. N counts represented physical pages, including provisioned spare space, rather than only host-visible logical addresses. Logarithmic Gecko instead buffers invalidations and stores merged summaries in flash. [1]
Sizing example: With 4 KiB pages, 1 TiB of represented physical space needs 32 MiB. Covering 1.25 TiB instead needs 40 MiB. For 1 TiB host-visible capacity, this is 25% additional physical space and an 8 MiB underestimate if sized from logical capacity alone. These are bitmap payloads, not total controller RAM. [4]
Relations
- related
- GeckoFTL, SSD mapping cache, Garbage collection (flash), Reverse mapping (FTL), NAND erase block, Flash translation layer (FTL)
Limitations
- A validity summary alone does not identify the logical owner of each physical page or establish crash-recovery ordering. [1, 2]
Citations
- Dayan, Bonnet and Idreos. GeckoFTL. SIGMOD 2016, sections 2-3.1; DOI 10.1145/2882903.2915219.
- Dayan and Bonnet. Garbage Collection Techniques for Flash-Resident Page-Mapping FTLs. arXiv:1504.01666v1, sections 3.1 and 5.
- Hesela: exact physical-page bitmap sizing examples (JavaScript).
Further reading
Sources & caveats
- The worked designs are research systems; status does not classify every commercial controller. No device measurements or implementation replication are supplied.
- Bit polarity follows the named Gecko designs, not a universal bitmap format. The 2015 precursor and the 2016 paper are distinct sources.
- The 2015 section 5.2.4 live-page Hamming-weight sentence conflicts with its section 5.1 definition and Algorithm 1 (1 means invalid); that count sentence is not used.
- Sizing examples are hypothetical exact arithmetic, not measurements of an SSD. The public script uses integer page counts and rounds partial bytes upward.