45.3 LargeSUT

LargeSUT is an implementation of the pure abstract interface ISUT when the SUT is too large to be stored in the root block, so it uses a two level hierarchical map.

Two-level representation

The root of the map is serialized into the root-block division. Its children are SUTSection objects, each occupying an entire segment and storing a contiguous array of 32-bit utilisations. SUTSectionRef records the SegId of a section and permits it to be loaded into memory when needed.

With 512 KiB segments, one SUT section contains 128 Ki utilisations and describes 64 GiB of store space. The root therefore needs relatively few section references even for a large store. Indexing is a direct two-level lookup.

Loading and dirty sections

SUT sections are loaded on demand. A utilisation update marks the containing section dirty. The current implementation does not evict resident sections; dirty sections in particular cannot be evicted until their state has been written by a checkpoint.

At startup the FSS is reconstructed by scanning zero utilisations, which currently causes all SUT sections to be loaded. This is acceptable for stores with few sections but would need a more scalable free-space discovery mechanism for very large stores.

Checkpoint and shadow paging

Dirty SUT sections are written using shadow paging. A checkpoint allocates fresh segments from the FSS rather than overwriting the sections referenced by the last valid root-block division. If the checkpoint fails, the previous sections therefore remain available to the previous checkpoint.

Writing a replacement section must not make the SUT a moving target. Segments occupied by SUT sections have zero packet utilisation and are protected with reservations. When a section is replaced, its previous segment is unreserved at the appropriate checkpoint. During deserialization, every referenced SUT-section segment is reserved; destruction releases those reservations.

LargeSUT exposes the SegIds occupied by its sections so that startup reconstruction does not mistake their zero utilisations for free segments.

Concurrency

LargeSUT is used through the SUT facade. Utilisation updates, allocation and checkpoint serialization are synchronized by that facade and the SegmentWriter/checkpoint protocol; the two-level map does not define an independent public locking policy.

Limitations

• SUT sections should be protected by a checksum.
• A scalable implementation needs eviction or another bounded residency policy.
• Startup should not require loading every SUT section merely to reconstruct free space.

Code

class LargeSUT : public ISUT
{
public:
    LargeSUT(LSS& lss, Reservations& reservations);
    ~LargeSUT();
    void Clear();
    void SetSegmentSize(int segmentSize);
    void Init(const SmallSUT& sm);
    void WriteDirtySUTSections(SUT& sut);
    void GetSegmentsUsedBySUTSections(std::set<SegId>& s) const;
    SegId GetLastSUTSection() const;
    virtual void Serialise(Archive& ar) const;
    virtual void Deserialise(InputArchive& ar);
    virtual int GetUtilisation(SegId segid) const;
    virtual void SetUtilisation(SegId segid, int u);
    virtual int GetTotalNumSegments() const;
    virtual void IncrementTotalNumSegments();

private:
    void AddSUTSection();
    SUTSection* GetSUTSection(SegId segid);

private:
    LSS& lss_;
    Reservations& reservations_;
    int segmentSize_;
    int numSegmentsPerSUTSection_;
    xvector<SUTSectionRef> sutSections_;
    int totalNumSegments_;
};