# Fewer mapping heads can still cost more bytes

Evidence: synthetic representation accounting, not device measurements or a
FlashSim reproduction. Python standard library only. No external data or seed.

## Reproduce

Run in this directory:

    python3 -B model.py --check
    python3 -B packed.py --check
    python3 -B -m unittest discover -s . -p 'test_*.py'
    python3 -B -O -m unittest discover -s . -p 'test_*.py'

model.py --write regenerates results.json. Its SHA-256 is embedded in the result.
All input physical addresses and track labels are retained in that JSON.

## Question and result

For 512 mappings, four-byte physical page numbers (PPNs), byte-packed bitmaps,
and only PPN payload in each stored head, an extra bitmap bit costs 64 bytes.
Saving one four-byte head cannot repay that cost. Two-bit representation needs
to save at least 17 heads for a strict byte reduction; saving 16 only ties.

The generated family starts with a contiguous physical run. It then replaces
k isolated, interior logical pages with new, distinct PPNs. Every replacement
is separated from the next by three unchanged positions. Supplied labels mark
old mappings as base and replacements as local.

| Replacements | One-bit heads | Two-bit heads | One-bit bytes | Two-bit bytes |
| --- | --- | --- | --- | --- |
| 0 | 1 | 1 | 68 | 132 |
| 1 | 3 | 2 | 76 | 136 |
| 16 | 33 | 17 | 196 | 196 |
| 17 | 35 | 18 | 204 | 200 |

These are exact outputs of specified synthetic inputs, not sampled estimates.
No confidence interval applies. They do not establish how often these states
occur in an SSD.

## Derivation

For N mappings, width w bytes per head and head counts H1/H2:

    C1 = ceil(N / 8) + w * H1
    C2 = ceil(2 * N / 8) + w * H2
    C2 < C1 iff w * (H1 - H2) > ceil(2 * N / 8) - ceil(N / 8)

Use byte rounding for arbitrary N. The family has H1=1+2k and H2=1+k.
At N=512, w=8 the strict crossover is nine saved heads, not seventeen.
Changing head layout, alignment or bookkeeping changes the arithmetic.

The eight-entry witness gives the opposite result: an interior two-page patch
needs three one-bit heads but two two-bit heads, giving 13 versus 10 modeled
bytes. Fewer heads and fewer bytes can coincide; neither implies the other
without the accounting parameters.

## Model boundary

The one-bit codec starts a head when adjacent PPNs stop increasing by one.
The two-bit codec takes explicit base/local labels: base segments can bridge
local patches; local runs restart after a base position. Distance is measured
in logical positions, including intervening positions. Both reconstruct exactly.

No label-selection policy, allocator, replacement policy, garbage collection,
dirty buffering, flash timing, crash recovery or CPU cost is simulated.
Costs include only rounded bitmap bytes and head PPNs. Directory, tags,
allocation headers, pointers, alignment and dirty/LRU state are excluded.
The Python objects are not controller-memory measurements.

The decoder checks structure, not authenticity: a changed head can produce a
different valid map. Lossless encoding is not corruption detection.

## Source context

Jiang et al., S-FTL, MSST 2011, III.B and Figure 3:
https://msstconference.org/MSST-history/2011/Papers/Research/4.Jiang.pdf

The conversion helper preserves strict below-80% and above-90% boundaries;
equality retains the current form. It is not a full cache simulation.
The paper reports a 70-byte single-head example; this payload model counts 68.
The difference is not silently corrected or assigned to an invented header.

## Checks and reuse

Tests enumerate injective maps over six PPN values, lengths one through six,
and every base/local labeling. A separate offset-change oracle checks head
counts. Boundary, invalid-input, missing-head, width and result-hash checks
also run with Python optimization enabled.

Original Hesela code and synthesis; cited papers and figures are not bundled.
Reuse follows the repository's applicable terms, with no new license assigned
to third-party work.

## Byte-level cross-check and history

The separate packed.py implementation materializes all sixteen forms of the
original eight witnesses. It stores only bitmap bits and PPNs: no head positions.
Its backward-search decoder reconstructs every original map. packed-results.json
retains exact hex, lengths, hashes and the frozen input-file digest. Bit order and
endianness are Hesela choices, not a recovered controller format. Parameters N,
bitmap width and PPN width are supplied externally; this is not a self-describing
storage format. Structural checks do not authenticate a valid changed address.

For the existing threshold helper, a 2048-byte flat map and a 1728-byte bitmap
have ratio 84.375%. Starting flat retains 2048 bytes; starting compressed retains
1728. A preceding bitmap cost of 1636 enters compression, whereas 1844 selects
flat. These are conditional size-state histories, not update traces or evidence
of a device's policy. With 512 entries and two bits each, 1728 corresponds to
400 four-byte heads. The possible 320-byte difference concerns this payload
model only, without inferring total RAM or latency.

Cache admission is a separate event: III.B selects bitmap on load only below
80%. Holding the candidate size fixed at 1728 bytes, a newly loaded page takes
the 2048-byte flat form, regardless of an earlier bitmap residency. At exactly
80%, a resident bitmap is retained but a fresh load is flat. This distinction
does not simulate eviction, retained dirty entries or any writeback IO.

S-FTL III.B also describes size-sensitive second chances in its replacement
policy; III.C separates sparse dirty entries from whole-page writeback.
SCFTL II-III discusses different cache granularities and dirty-victim costs:
https://www.cp.eng.chula.ac.th/~prabhas/paper/2014/pera-ICSEC-2.pdf

Comparison contract: report the cached unit, charged bytes, starting form,
transition thresholds, admission/replacement and writeback rules. Identical
mapping content and nominal cache capacity are not a complete experimental
specification. No performance comparison is computed here.