45.6 Free Segment Stack (FSS)

The Free Segment Stack (FSS) contains the SegIds that may be allocated and overwritten immediately. It is distinct from the SUT: a zero utilisation is necessary for ordinary packet segments to become free, but is not by itself permission to reuse a segment.

FSS and delta-FSS

The LSS maintains an FSS and a delta-FSS. When a segment becomes eligible to be freed, its SegId is first added to the delta-FSS. The delta-FSS records segments freed since the last valid checkpoint. Those segments cannot yet be overwritten because recovery from that checkpoint may still need to scan them.

After a new checkpoint has been published successfully, the delta-FSS is transferred to the FSS. The segments are then old enough to be reused without invalidating recovery from the latest checkpoint. This delayed transfer is a central storage-safety rule.

Allocation

When the SegmentWriter needs a new segment, it pops a SegId from the FSS. If the FSS is empty, it allocates a previously unused SegId beyond the current end of the store. The FSS is kept in an order that encourages heavy log writing to proceed through nearby file ranges and preserve clustering.

Allocating a segment implicitly reserves it. The caller must later unreserve it. This prevents a newly allocated current or preallocated segment from being returned to the delta-FSS merely because its utilisation is temporarily zero.

Initialisation at startup

The FSS is deliberately not serialized in the root block or elsewhere on disk. It is derived state: the persisted SUT records which ordinary packet segments have zero utilisation, while the reservation state identifies zero-utilisation segments that are nevertheless occupied for an internal purpose. Reconstructing the FSS from these authoritative inputs avoids maintaining another check-pointed structure whose contents would have to be kept consistent with the SUT.

After reading the SUT from the selected valid root-block division, the implementation clears both the FSS and delta-FSS and scans every allocated SegId, starting at SegId 1 and proceeding in ascending order. A SegId is added to the FSS precisely when its stored utilisation is zero and it is not reserved. This scan necessarily reads the utilisation of every segment and, for a LargeSUT, faults the complete SUT into memory.

Reservations are essential to the reconstruction. Segments occupied by LargeSUT sections have zero packet utilisation because SUT-section data is not counted as live packet data, but those segments are not free. Before scanning, LargeSUT reports the set of SegIds occupied by the SUT sections referenced by the valid checkpoint. Those segments are represented as reserved and are therefore excluded from the reconstructed FSS. The implementation also verifies in diagnostic assertions that membership of this set agrees with the reservation state.

Scanning SegIds in ascending order creates an FSS ordered from the front of the file towards the end. Allocation removes the first entry, so the lowest available SegId is normally reused first. The same policy is restored when newly safe entries are transferred from the delta-FSS: the implementation sorts the combined FSS by SegId. This ordering has two intended benefits. Consecutive allocations are more likely to refer to nearby file locations, which helps keep the writing of large serial elements clustered, and reuse is biased towards the beginning of the file, leaving free segments near the end and making eventual file truncation more feasible. Despite the historical names Free Segment Stack and SegIdStack, allocation is therefore not LIFO stack ordering.

The delta-FSS always starts empty. Its meaning is relative to the checkpoint from which the store is being recovered: it contains segments that became free after that checkpoint and which cannot yet be overwritten safely. At the instant represented by the selected checkpoint there are no such post-checkpoint transitions. Any allocation and freeing activity recorded later in the log is dealt with by recovery replay rather than being guessed during initial reconstruction. This preserves the rule that a segment needed to scan and recover records after the last valid checkpoint must not be reused prematurely.

When utilisation falls to zero

When a segment's utilisation falls to zero, it normally becomes a candidate for the delta-FSS. It is added only when it has no reservations. Conceptually, for segment s with utilisation u(s) and reservation count r(s), the transition occurs when both values are zero.

Reservations handle cases in which zero utilisation is transient or does not mean that access has finished. These include the segment currently being prepared by the SegmentWriter, a preallocated next segment, a reader still using an obsolete packet, and a segment holding a LargeSUT section.

A segment enters the delta-FSS only when its utilisation and reservation count are both zero. A successful checkpoint transfers it to the FSS, and allocation makes it reserved and unavailable for reuse again.

Recovery replay

Recovery scans the log after the last valid checkpoint and replays segment allocation history. A segment that was originally allocated with AllocateSegId() is reallocated during replay with AllocateGivenSegId(). Snapshot boundaries determine when the allocation and unreservation transitions are replayed.

Concurrency

The current FSS is protected by the SUT facade's mutex. This is required because checkpoint activity can transfer segments into the FSS outside the SegmentWriter lock. FSS and delta-FSS transitions must be serialized with utilisation and reservation changes so that a segment cannot be made available while it is still protected.

Implementation

The FSS and delta-FSS use SegIdStack, which derives from std::deque<SegId>. Their ownership and operations are currently implemented by the SUT facade rather than by a separate FSS class.