#include <Cache.h>

Collaboration diagram for Cache:

Classes
struct	BackgroundWriteback

struct	CachePage

struct	callbackMeta

class	DirectWritebackLease

struct	DiscardReference

class	PreparedDiscard

struct	WritebackPage

Public Types
enum class	ShutdownMode { WriteBack , Discard , DiscardDeferred }

enum class	DirtyTracking { Checksum , Explicit }

enum class	DiscardStatus { Ready , NoMemory , Busy , Invalid , Closed }

typedef bool(*	writeback_t) (CacheConstants::CallbackCause cause, uintptr_t loc, uintptr_t page, void *meta)

typedef bool(*	retirement_writeback_t) (uintptr_t key, uintptr_t page, void *meta)

using	writeback_batch_t = bool()(const WritebackPage , size_t, void *)

Public Member Functions
	Cache (size_t pageConstraints=0)

bool	shutdown (ShutdownMode mode=ShutdownMode::WriteBack)

void	setCallback (writeback_t newCallback, void *meta)

void	setDirtyTracking (DirtyTracking tracking)

uintptr_t	lookup (uintptr_t key)

size_t	read (uintptr_t offset, size_t length, uintptr_t buffer, bool(*prepare)(uintptr_t, size_t)=nullptr)

MUST_USE_RESULT bool	lookupStable (uintptr_t key, uintptr_t &location, bool wait=false)

uintptr_t	insert (uintptr_t key, bool *alreadyExisted=nullptr)

uintptr_t	insert (uintptr_t key, size_t size, bool *alreadyExisted=nullptr)

bool	exists (uintptr_t key, size_t length)

bool	evict (uintptr_t key)

MUST_USE_RESULT bool	discardEditing (uintptr_t key)

MUST_USE_RESULT bool	retireWriteback (uintptr_t key, retirement_writeback_t callback, void *meta)

bool	empty ()

DiscardStatus	prepareDiscardFrom (uintptr_t cutoff, const DiscardReference *references, size_t count, UniquePointer< PreparedDiscard > &result)

void	release (uintptr_t key)

MUST_USE_RESULT bool	pin (uintptr_t key)

size_t	trim (size_t count=1)

bool	sync (uintptr_t key, bool async)

MUST_USE_RESULT bool	syncAll ()

void	setBackgroundWriteback (writeback_batch_t callback)

MUST_USE_RESULT bool	syncAll (writeback_batch_t callback, void *metadata)

MUST_USE_RESULT bool	syncBatch (const uintptr_t keys, size_t count, writeback_batch_t callback, void metadata)

void	triggerChecksum (uintptr_t key)

void	markDirty (uintptr_t key)

void	markExternallyWritable (uintptr_t key)

MUST_USE_RESULT bool	beginMutableLoan (uintptr_t key)

void	endMutableLoan (uintptr_t key)

void	startAtomic ()

void	endAtomic ()

void	markEditing (uintptr_t key, size_t length=0)

void	markNoLongerEditing (uintptr_t key, size_t length=0)

virtual bool	needsPeriodicTimer () const

virtual void	timer (uint64_t delta)

virtual uint64_t	executeRequest (uint64_t p1, uint64_t p2, uint64_t p3, uint64_t p4, uint64_t p5, uint64_t p6, uint64_t p7, uint64_t p8)

Static Public Attributes
static constexpr size_t	MaxWritebackPages = 64

Private Types
enum class	EvictionMode { Ordinary , DiscardBaseReference , DiscardEditing , DiscardDirty }

Private Member Functions
bool	map (uintptr_t virt) const

bool	evict (uintptr_t key, EvictionMode mode, size_t *discardedDirtyPages=nullptr)

bool	empty (EvictionMode mode, size_t *discardedDirtyPages, bool waitForPins=true)

bool	finishRetirement (CachePage page, writeback_t callback, void callbackMeta)

void	releaseWriteback (uintptr_t key)

void	waitForPageEviction (uintptr_t key)

bool	ensureUsable (const char *operation) const

size_t	lruEvict (bool force=false)

void	linkPage (CachePage *pPage)

void	promotePage (CachePage *pPage)

void	unlinkPage (CachePage *pPage)

void	calculateChecksum (CachePage *pPage)

bool	verifyChecksum (CachePage *pPage, bool replace=false)

bool	tracksChecksum (const CachePage *page) const

bool	needsWriteback (CachePage *page)

void	updateWritebackIndex (CachePage *page)

void	recordMutation (CachePage *page)

void	checksum (const void *data, size_t len, uint64_t out[2])

void	releaseBackgroundWriteback (BackgroundWriteback *batch)

bool	syncBatchInternal (const uintptr_t keys, size_t count, writeback_batch_t callback, void metadata, bool snapshot)

bool	writebackPage (uintptr_t key, uintptr_t location, bool wait)

Static Private Member Functions
static void	discover_range (uintptr_t &start, uintptr_t &end)

Private Attributes
Tree< uintptr_t, CachePage * >	m_Pages

Tree< uintptr_t, CachePage * >	m_WritebackPages

DirtyTracking	m_DirtyTracking

BloomFilter< uintptr_t >	m_PageFilter

CachePage *	m_pLruHead

CachePage *	m_pLruTail

Spinlock	m_Lock

WaitQueue	m_EvictionWaiters

OperationBarrier	m_ManagerOperations

uint64_t	m_ManagerId

CacheManager::TimerStamp	m_ManagerTimerStamp

bool	m_PeriodicTimerEnabled

writeback_t	m_Callback

writeback_batch_t	m_BackgroundWriteback

uint64_t	m_Nanoseconds

uint64_t	m_WritebackEpoch

void *	m_CallbackMeta

Atomic< size_t >	m_bInCritical

Atomic< size_t >	m_ShutdownState

size_t	m_PageConstraints

Static Private Attributes
static MemoryAllocator	m_Allocator

static Spinlock	m_AllocatorLock

Friends
class	CacheManager

class	CacheMemoryTestPeer

Detailed Description

Provides an abstraction of a data cache.

Definition at line 207 of file Cache.h.

Member Typedef Documentation

◆ retirement_writeback_t

typedef bool(* Cache::retirement_writeback_t) (uintptr_t key, uintptr_t page, void *meta)

Synchronous writeback used immediately before retiring one page.

Definition at line 293 of file Cache.h.

◆ writeback_batch_t

using Cache::writeback_batch_t = bool (*)(const WritebackPage*, size_t, void*)

Definition at line 542 of file Cache.h.

◆ writeback_t

typedef bool(* Cache::writeback_t) (CacheConstants::CallbackCause cause, uintptr_t loc, uintptr_t page, void *meta)

Callback type: for functions called by the write-back timer handler.

The write-back handler checks all pages in the cache at a regular interval. If it finds a dirty page, it calls the Cache callback, which should write the modified data back to a backing store, if any exists.

Return false when backing-store submission or completion fails. The page remains dirty and ordinary eviction must retain it for a later retry.

Definition at line 289 of file Cache.h.

Member Enumeration Documentation

◆ DirtyTracking

enum class Cache::DirtyTracking

strong

Definition at line 327 of file Cache.h.

◆ DiscardStatus

enum class Cache::DiscardStatus

strong

Definition at line 436 of file Cache.h.

◆ EvictionMode

enum class Cache::EvictionMode

strongprivate

Definition at line 631 of file Cache.h.

◆ ShutdownMode

enum class Cache::ShutdownMode

strong

Definition at line 302 of file Cache.h.

Constructor & Destructor Documentation

◆ Cache()

Cache::Cache ( size_t pageConstraints = 0 )

Definition at line 604 of file Cache.cc.

◆ ~Cache()

Cache::~Cache ( )

virtual

Definition at line 659 of file Cache.cc.

Member Function Documentation

◆ beginMutableLoan()

bool Cache::beginMutableLoan ( uintptr_t key )

Tracks a bounded writable alias. The caller already owns a page reference and must retain it until after the matching endMutableLoan(). Overlapping loans share checksum tracking; returning the last loan preserves any dirty data before removing temporary tracking. External mappings remain tracked.

Definition at line 2160 of file Cache.cc.

References calculateChecksum(), ensureUsable(), ProcessorBase::information(), m_EvictionWaiters, m_Lock, and m_Pages.

Referenced by ScsiDisk::pin(), and ScsiDisk::zero().

Here is the caller graph for this function:

◆ calculateChecksum()

void Cache::calculateChecksum ( CachePage * pPage )

private

Calculate a checksum for the given CachePage.

Definition at line 2553 of file Cache.cc.

References checksum(), Cache::CachePage::checksum, and Cache::CachePage::location.

Referenced by beginMutableLoan(), markExternallyWritable(), markNoLongerEditing(), and triggerChecksum().

Here is the caller graph for this function:

◆ checksum()

void Cache::checksum	(	const void *	data,
		size_t	len,
		uint64_t	out[2]
	)

private

Checksum do-er.

Definition at line 2609 of file Cache.cc.

Referenced by calculateChecksum(), Cache::CachePage::checkZeroChecksum(), evict(), verifyChecksum(), and writebackPage().

Here is the caller graph for this function:

◆ discardEditing()

bool Cache::discardEditing ( uintptr_t key )

Discards a failed cache fill before it is published.

This succeeds only for an Editing page with exactly its insertion-time reference. It never removes an externally pinned page and does not write failed data back to the backing store.

Definition at line 1129 of file Cache.cc.

References ensureUsable(), and evict().

Referenced by FileDisk::read(), and RawFsFile::readBlock().

Here is the caller graph for this function:

◆ discover_range()

static void Cache::discover_range	(	uintptr_t &	start,
		uintptr_t &	end
	)

staticprivate

Determines the range of addresses permitted for use for Cache.

◆ empty() [1/2]

bool Cache::empty ( )

Empties the cache.

Waits for external pins, then discards each page's publication-time base reference. Concurrent same-key eviction is joined safely.

Definition at line 1467 of file Cache.cc.

References empty(), and ensureUsable().

Referenced by empty(), shutdown(), and Ext2File::~Ext2File().

Here is the caller graph for this function:

◆ empty() [2/2]

bool Cache::empty	(	EvictionMode	mode,
		size_t *	discardedDirtyPages,
		bool	waitForPins = `true`
	)

private

Definition at line 1474 of file Cache.cc.

◆ endAtomic()

void Cache::endAtomic ( )

inline

Leaves the critical section for this cache.

Definition at line 604 of file Cache.h.

◆ endMutableLoan()

void Cache::endMutableLoan ( uintptr_t key )

Definition at line 2206 of file Cache.cc.

◆ ensureUsable()

bool Cache::ensureUsable ( const char * operation ) const

private

Rejects use after the terminal shutdown contract has completed.

Definition at line 700 of file Cache.cc.

References m_ShutdownState.

Referenced by beginMutableLoan(), discardEditing(), empty(), evict(), exists(), insert(), insert(), lookup(), lookupStable(), markDirty(), markEditing(), markExternallyWritable(), markNoLongerEditing(), pin(), read(), release(), retireWriteback(), setDirtyTracking(), sync(), timer(), triggerChecksum(), and trim().

Here is the caller graph for this function:

◆ evict() [1/2]

bool Cache::evict ( uintptr_t key )

Evicts the given key from the cache, also freeing the memory it holds.

This will respect the refcount of the given key, so as to make pin() exhibit more reliable behaviour.

Definition at line 1122 of file Cache.cc.

References ensureUsable(), and evict().

Referenced by discardEditing(), evict(), executeRequest(), lruEvict(), and read().

Here is the caller graph for this function:

◆ evict() [2/2]

bool Cache::evict	(	uintptr_t	key,
		EvictionMode	mode,
		size_t *	discardedDirtyPages = `nullptr`
	)

private

Retires one page according to the caller's refcount contract.

Definition at line 1136 of file Cache.cc.

References checksum(), Cache::CachePage::checksum, finishRetirement(), ProcessorBase::information(), Cache::CachePage::location, m_Callback, m_CallbackMeta, m_EvictionWaiters, m_Lock, m_PageFilter, m_Pages, and Cache::CachePage::refcnt.

◆ executeRequest()

uint64_t Cache::executeRequest	(	uint64_t	p1,
		uint64_t	p2,
		uint64_t	p3,
		uint64_t	p4,
		uint64_t	p5,
		uint64_t	p6,
		uint64_t	p7,
		uint64_t	p8
	)

virtual

RequestQueue doer, called by the CacheManager instance.

Definition at line 2449 of file Cache.cc.

References evict(), m_CallbackMeta, m_Lock, m_Pages, Cache::CachePage::refcnt, and writebackPage().

Referenced by CacheManager::executeRequest().

Here is the caller graph for this function:

◆ exists()

bool Cache::exists	(	uintptr_t	key,
		size_t	length
	)

Checks if the entire range specified exists in the cache.

Definition at line 1098 of file Cache.cc.

References ensureUsable(), m_Lock, m_PageFilter, and m_Pages.

◆ finishRetirement()

bool Cache::finishRetirement	(	CachePage *	page,
		writeback_t	callback,
		void *	callbackMeta
	)

private

Completes retirement after the caller publishes Retiring under m_Lock.

Definition at line 1282 of file Cache.cc.

References RangeList< T, Reversed >::free(), PhysicalMemoryManager::freePage(), VirtualAddressSpace::getMapping(), ProcessorBase::information(), PhysicalMemoryManager::instance(), Cache::CachePage::key, Cache::CachePage::location, m_Allocator, m_AllocatorLock, m_EvictionWaiters, m_Lock, m_PageFilter, m_Pages, m_WritebackPages, unlinkPage(), and VirtualAddressSpace::unmap().

Referenced by evict(), and retireWriteback().

Here is the caller graph for this function:

◆ insert() [1/2]

uintptr_t Cache::insert	(	uintptr_t	key,
		bool *	alreadyExisted = `nullptr`
	)

Creates a cache entry with the given key.

The new entry will already be marked as being edited, and so won't be written back until the inserter calls markNoLongerEditing again.

The returned address never carries a caller-owned reference: a new entry has only its publication reference, and an existing entry may still be Editing. Serialise same-key fills, publish new data, then use lookup() when the caller needs a lifetime reference.

Parameters

alreadyExisted can be used to find out if the return value is a page that already existed and no mapping was completed.

Todo:: remove this, it makes the bloom filter pointless

Definition at line 890 of file Cache.cc.

References Spinlock::acquire(), RangeList< T, Reversed >::allocate(), Cache::CachePage::checksum, ensureUsable(), Cache::CachePage::key, linkPage(), Cache::CachePage::location, lruEvict(), m_Allocator, m_AllocatorLock, m_Lock, m_PageFilter, m_Pages, map(), Cache::CachePage::refcnt, Spinlock::release(), and waitForPageEviction().

Referenced by RamFile::allocateFileRange(), AtaDisk::doRead(), ScsiDisk::doRead(), DiskImage::read(), FileDisk::read(), RawFsFile::readBlock(), FatFile::readBlock(), RamFile::readBlock(), File::readIntoCache(), and ScsiDisk::zero().

Here is the caller graph for this function:

◆ insert() [2/2]

uintptr_t Cache::insert	(	uintptr_t	key,
		size_t	size,
		bool *	alreadyExisted = `nullptr`
	)

Creates a bunch of cache entries to fill a specific size. Note that this is just a monster allocation of a virtual address - the physical pages are NOT CONTIGUOUS.

The operation is all-or-nothing. A complete, contiguous existing range is returned unchanged; any partial overlap rejects the insertion before virtual address space or physical pages are allocated. A size that is not a whole number of target pages is rejected rather than truncated.

As with the single-page overload, the returned address carries no caller-owned lifetime reference.

Parameters

alreadyExisted is true only when the complete contiguous range already existed. It is false for a new range or a rejected partial overlap.

Definition at line 963 of file Cache.cc.

References Spinlock::acquire(), RangeList< T, Reversed >::allocate(), Cache::CachePage::checksum, Dec, ensureUsable(), Hex, Cache::CachePage::key, linkPage(), Cache::CachePage::location, lruEvict(), m_Allocator, m_AllocatorLock, m_Lock, m_PageFilter, m_Pages, map(), Cache::CachePage::refcnt, Spinlock::release(), and waitForPageEviction().

◆ linkPage()

void Cache::linkPage ( CachePage * pPage )

private

Link the given CachePage to the LRU list.

Definition at line 2527 of file Cache.cc.

References m_pLruHead, and Cache::CachePage::pNext.

Referenced by insert(), insert(), and promotePage().

Here is the caller graph for this function:

◆ lookup()

uintptr_t Cache::lookup ( uintptr_t key )

Looks for key , increasing refcnt by one if returned.

Definition at line 737 of file Cache.cc.

References ensureUsable(), Cache::CachePage::location, m_Lock, m_PageFilter, m_Pages, promotePage(), and Cache::CachePage::refcnt.

Referenced by RamFile::acquireCachedBlock(), RamFile::allocateFileRange(), File::allocateRange(), AtaDisk::doRead(), ScsiDisk::doRead(), FatFile::extend(), File::getPhysicalPage(), DiskImage::read(), FileDisk::read(), RawFsFile::readBlock(), FatFile::readBlock(), RamFile::readBlock(), File::readIntoCache(), File::resize(), ScsiDisk::sync(), File::syncFillCache(), File::syncRange(), ScsiDisk::write(), and ScsiDisk::zero().

Here is the caller graph for this function:

◆ lookupStable()

bool Cache::lookupStable	(	uintptr_t	key,
		uintptr_t &	location,
		bool	wait = `false`
	)

Pins a published page, or returns true with location zero for a confirmed miss. Optional waiting joins callbacks and eviction, never publication or a drain of external loans. Callers must release backend range locks before waiting and revalidate after reacquiring them. Existing pins are allowed.

Definition at line 844 of file Cache.cc.

References ensureUsable(), ProcessorBase::information(), Cache::CachePage::location, m_EvictionWaiters, m_Lock, m_ManagerOperations, m_PageFilter, m_Pages, promotePage(), Cache::CachePage::refcnt, and OperationBarrier::tryAcquire().

Referenced by ScsiDisk::readIntoBatch(), and ScsiDisk::writeFromBatch().

Here is the caller graph for this function:

◆ lruEvict()

size_t Cache::lruEvict ( bool force = false )

private

LRU evict do-er.

Parameters

force force an eviction to be attempted

Returns: number of cache pages evicted

Definition at line 2488 of file Cache.cc.

References evict(), PhysicalMemoryManager::instance(), Cache::CachePage::key, m_Lock, m_PageFilter, m_Pages, m_pLruHead, and promotePage().

Referenced by insert(), insert(), and trim().

Here is the caller graph for this function:

◆ map()

bool Cache::map ( uintptr_t virt ) const

private

mapping doer

Definition at line 1086 of file Cache.cc.

References PhysicalMemoryManager::allocatePage(), ProcessorBase::information(), PhysicalMemoryManager::instance(), VirtualAddressSpace::KernelMode, m_PageConstraints, and VirtualAddressSpace::Write.

Referenced by insert(), and insert().

Here is the caller graph for this function:

◆ markDirty()

void Cache::markDirty ( uintptr_t key )

Records a modification, including one made during an active writeback.

Definition at line 2135 of file Cache.cc.

References ensureUsable(), m_Lock, and m_Pages.

Referenced by File::allocateRange(), FatFile::extend(), File::resize(), ScsiDisk::write(), FatFile::writeBlock(), RawFsFile::writeBlock(), Ext2File::writeBlocks(), and ScsiDisk::zero().

Here is the caller graph for this function:

◆ markEditing()

void Cache::markEditing	(	uintptr_t	key,
		size_t	length = `0`
	)

Mark the given page as being edited.

A page being edited will never be written back, nor will its checksum be calculated. Once a page is no longer being edited, it goes into an intermediate mode that means it'll have its checksum calculated asynchronously. After that point, normal checksum-based writebacks take place. A nonzero length must be a whole number of target pages; invalid ranges are left unchanged.

Definition at line 2613 of file Cache.cc.

References ensureUsable(), m_Lock, m_PageFilter, and m_Pages.

◆ markExternallyWritable()

void Cache::markExternallyWritable ( uintptr_t key )

Enables checksum detection before exposing a writable external mapping. The fallback remains active for this page's entire residency.

Definition at line 2146 of file Cache.cc.

References calculateChecksum(), ensureUsable(), m_Lock, and m_Pages.

Referenced by File::markPageExternallyWritable().

Here is the caller graph for this function:

◆ markNoLongerEditing()

void Cache::markNoLongerEditing	(	uintptr_t	key,
		size_t	length = `0`
	)

Mark the given page as no longer being edited. A nonzero length must be a whole number of target pages; invalid ranges are left unchanged.

Definition at line 2646 of file Cache.cc.

References calculateChecksum(), ensureUsable(), m_Lock, m_PageFilter, and m_Pages.

Referenced by RamFile::allocateFileRange(), DiskImage::read(), FileDisk::read(), RawFsFile::readBlock(), FatFile::readBlock(), RamFile::readBlock(), File::readIntoCache(), and ScsiDisk::zero().

Here is the caller graph for this function:

◆ needsPeriodicTimer()

virtual bool Cache::needsPeriodicTimer ( ) const

inlinevirtual

Called under the manager registry lock; overrides must not block or acquire cache locks. Custom timers independent of writeback must opt in here.

Definition at line 715 of file Cache.h.

◆ needsWriteback()

bool Cache::needsWriteback ( CachePage * page )

private

Definition at line 2582 of file Cache.cc.

◆ pin()

bool Cache::pin ( uintptr_t key )

Increases key 's refcnt by one.

This is used for places that, for example, use the physical address of a cache page and therefore will never set the dirty flag of a virtual page. This use case will need to provide its own means for writing data back to the backing store, if that is desirable.

Pinned pages will not be freed during a compact().

Returns: false if key didn't exist, true otherwise

Definition at line 1544 of file Cache.cc.

References ensureUsable(), m_Lock, m_PageFilter, m_Pages, promotePage(), and Cache::CachePage::refcnt.

Referenced by ScsiDisk::pin(), DiskImage::pin(), FileDisk::pin(), RawFsFile::pinBlock(), FatFile::pinBlock(), and RamFile::pinBlock().

Here is the caller graph for this function:

◆ prepareDiscardFrom()

Cache::DiscardStatus Cache::prepareDiscardFrom	(	uintptr_t	cutoff,
		const DiscardReference *	references,
		size_t	count,
		UniquePointer< PreparedDiscard > &	result
	)

The owner serializes fills and retires the plan on its creating thread. Keys are sorted and unique; references exclude publication and writeback pins. Commit follows release of the admitted references. Dropping the plan restores admission without discarding data.

Definition at line 109 of file Cache-discard.cc.

References UniquePointer< T >::adopt(), m_EvictionWaiters, m_Lock, m_ManagerOperations, m_Pages, m_ShutdownState, Cache::CachePage::refcnt, and OperationBarrier::tryAcquire().

Referenced by File::resize().

Here is the caller graph for this function:

◆ promotePage()

void Cache::promotePage ( CachePage * pPage )

private

Promote the given CachePage within the LRU list.

This marks the page as the most-recently-used page.

Definition at line 2537 of file Cache.cc.

References linkPage(), and unlinkPage().

Referenced by lookup(), lookupStable(), lruEvict(), pin(), read(), sync(), and timer().

Here is the caller graph for this function:

◆ read()

size_t Cache::read	(	uintptr_t	offset,
		size_t	length,
		uintptr_t	buffer,
		bool(*)(uintptr_t, size_t)	prepare = `nullptr`
	)

Copies a resident prefix, stopping at an unpublished/missing page or after 32 pages. The caller keeps this Cache alive and serializes content changes; this operation pins storage while copying without holding the cache lock. A null buffer probes and promotes the same prefix without copying. prepare may validate/make the destination writable after pins are acquired and the cache lock is released. Returning false releases the pins without copying.

Definition at line 769 of file Cache.cc.

References CacheManager::addCacheRequest(), ensureUsable(), evict(), m_EvictionWaiters, m_Lock, m_Pages, promotePage(), Cache::CachePage::refcnt, and WaitQueue::wakeAllIfWaiting().

Referenced by File::read(), and File::readCached().

Here is the caller graph for this function:

◆ recordMutation()

void Cache::recordMutation ( CachePage * page )

private

Definition at line 2602 of file Cache.cc.

◆ release()

void Cache::release ( uintptr_t key )

Decreases key 's refcnt by one.

Definition at line 1570 of file Cache.cc.

References CacheManager::addCacheRequest(), ensureUsable(), m_EvictionWaiters, m_Lock, m_PageFilter, m_Pages, m_ShutdownState, and Cache::CachePage::refcnt.

Referenced by RamFile::allocateFileRange(), File::allocateRange(), AtaDisk::doRead(), ScsiDisk::doRead(), AtaDisk::doWrite(), FatFile::extend(), File::getPhysicalPage(), ScsiDisk::pin(), ScsiDisk::readIntoBatch(), File::readIntoCache(), File::releaseReadReference(), File::resize(), File::returnPhysicalPage(), File::syncFillCache(), File::syncRange(), DiskImage::unpin(), FileDisk::unpin(), RawFsFile::unpinBlock(), FatFile::unpinBlock(), RamFile::unpinBlock(), ScsiDisk::write(), RawFsFile::writeBlock(), ScsiDisk::writeFromBatch(), and ScsiDisk::zero().

Here is the caller graph for this function:

◆ releaseBackgroundWriteback()

void Cache::releaseBackgroundWriteback ( BackgroundWriteback * batch )

private

Definition at line 2424 of file Cache.cc.

◆ releaseWriteback()

void Cache::releaseWriteback ( uintptr_t key )

private

Definition at line 235 of file Cache-discard.cc.

◆ retireWriteback()

bool Cache::retireWriteback	(	uintptr_t	key,
		retirement_writeback_t	callback,
		void *	meta
	)

Prevents new users of a published page, waits for its existing users and queued writebacks, and retires it after a successful synchronous writeback. The callback must use the supplied page directly and must not re-enter this Cache.

A missing page is already retired and succeeds without invoking the callback. Editing or concurrently retiring pages are left unchanged and fail immediately.

Definition at line 1336 of file Cache.cc.

References ensureUsable(), finishRetirement(), ProcessorBase::information(), Cache::CachePage::location, m_Callback, m_CallbackMeta, m_EvictionWaiters, m_Lock, m_PageFilter, m_Pages, WaitQueue::Guard::prepareToWait(), and Cache::CachePage::refcnt.

Referenced by ScsiDisk::retireCachePage().

Here is the caller graph for this function:

◆ setBackgroundWriteback()

void Cache::setBackgroundWriteback ( writeback_batch_t callback )

Optional durable timer callback, installed before pages; shares setCallback metadata.

Definition at line 2414 of file Cache.cc.

References m_Callback, m_Lock, m_Pages, and m_ShutdownState.

Referenced by Ext2File::Ext2File().

Here is the caller graph for this function:

◆ setCallback()

void Cache::setCallback	(	Cache::writeback_t	newCallback,
		void *	meta
	)

Installs the write-back callback before the Cache is used.

Callback metadata remains owned by the caller and must outlive the Cache. Replacing or clearing a callback is deliberately unsupported.

Definition at line 2390 of file Cache.cc.

References m_Callback, m_CallbackMeta, m_Lock, m_Pages, and m_ShutdownState.

Referenced by File::enableFillCacheWriteback(), Ext2File::Ext2File(), and RawFsFile::RawFsFile().

Here is the caller graph for this function:

◆ setDirtyTracking()

void Cache::setDirtyTracking ( DirtyTracking tracking )

Selects dirty tracking before inserting pages. Checksum is the default. Explicit owners must markDirty after every modification of published data.

Definition at line 2430 of file Cache.cc.

References ensureUsable(), m_Lock, and m_Pages.

Referenced by Ext2File::Ext2File(), and Iso9660File::Iso9660File().

Here is the caller graph for this function:

◆ shutdown()

bool Cache::shutdown ( ShutdownMode mode = ShutdownMode::WriteBack )

Drains manager-owned work and retires every page. Discard is reserved for removal of an unavailable backing device and reports lost dirty pages.

Owners whose callback metadata points at an enclosing object must call this at the start of that object's teardown, while callback dependencies are still alive. Calling it again after completion is harmless. A failed terminal drain reports false and retains unwritten storage; it cannot continue retries after its backend is destroyed. DiscardDeferred closes admission and drains callbacks immediately, but leaves pinned pages resident until a later shutdown or destruction. The cache and callback metadata must survive until all loans are returned.

Definition at line 663 of file Cache.cc.

References Dec, empty(), and m_ShutdownState.

Referenced by ScsiDisk::shutdownCache().

Here is the caller graph for this function:

◆ startAtomic()

void Cache::startAtomic ( )

inline

Enters a critical section with respect to this cache. That is, do not permit write back callbacks to be fired (aside from as a side effect of eviction) until the section has been left.

This is especially useful for an 'insert then read into buffer' operation, which can cause a writeback in the middle of reading (when nothing has actually changed at all).

Definition at line 594 of file Cache.h.

◆ sync()

bool Cache::sync	(	uintptr_t	key,
		bool	async
	)

Synchronises the given cache key back to a backing store, if a callback has been assigned to the Cache. Synchronous calls report the callback result; asynchronous calls report queue admission only. Clean pages need no payload callback; owners must still flush hardware.

Definition at line 1627 of file Cache.cc.

References CacheManager::addCacheRequest(), ensureUsable(), Cache::CachePage::location, m_Callback, m_Lock, m_PageFilter, m_Pages, promotePage(), and Cache::CachePage::refcnt.

Referenced by RawFsFile::sync(), FatFile::sync(), ScsiDisk::sync(), and File::syncFillCache().

Here is the caller graph for this function:

◆ syncAll() [1/2]

bool Cache::syncAll ( )

Synchronously writes a pinned snapshot, retaining failed pages for retry. A callback may drain a lower cache directly; a recursive or queue-dependent wait reports failure instead of deadlocking the shared CacheManager.

Definition at line 1687 of file Cache.cc.

References syncAll().

Referenced by RawFsFile::sync(), Ext2File::sync(), FatFile::sync(), FatFilesystem::sync(), ScsiDisk::syncAll(), and syncAll().

Here is the caller graph for this function:

◆ syncAll() [2/2]

bool Cache::syncAll	(	writeback_batch_t	callback,
		void *	metadata
	)

Submit the pinned dirty snapshot to one durable callback, including checksum-tracked aliases. The callback bounds its own I/O submission waves; no page is settled before its shared durability result.

Definition at line 1691 of file Cache.cc.

References Vector< T >::count(), ProcessorBase::information(), Cache::CachePage::key, Cache::CachePage::location, m_Callback, m_EvictionWaiters, m_Lock, m_ManagerOperations, m_Pages, m_ShutdownState, m_WritebackPages, Vector< T >::pushBack(), Cache::CachePage::refcnt, Vector< T >::size(), OperationBarrier::tryAcquire(), and writebackPage().

◆ syncBatch()

bool Cache::syncBatch	(	const uintptr_t *	keys,
		size_t	count,
		writeback_batch_t	callback,
		void *	metadata
	)

Claims up to MaxWritebackPages distinct resident pages for one durable callback. No page is settled or released before the shared result; a failed callback leaves every submitted page retryable. Clean pages are omitted, so the callback can receive fewer pages than requested or be skipped entirely. Owners must still flush hardware. Keys must remain valid for this call.

Definition at line 1834 of file Cache.cc.

Referenced by FatFile::sync(), ScsiDisk::sync(), ScsiDisk::syncPages(), Ext2File::syncPages(), and FatFile::syncPages().

Here is the caller graph for this function:

◆ syncBatchInternal()

bool Cache::syncBatchInternal	(	const uintptr_t *	keys,
		size_t	count,
		writeback_batch_t	callback,
		void *	metadata,
		bool	snapshot
	)

private

Definition at line 1894 of file Cache.cc.

◆ timer()

void Cache::timer ( uint64_t delta )

virtual

Cache timer handler.

Will call callbacks as needed to write dirty pages back to the backing store. The default eligibility predicate enables periodic dispatch after a writeback callback is installed.

Definition at line 2248 of file Cache.cc.

References CacheManager::addCacheRequest(), ensureUsable(), Hex, LIKELY, Cache::CachePage::location, m_bInCritical, m_Callback, m_Lock, m_Nanoseconds, m_Pages, m_WritebackPages, promotePage(), Cache::CachePage::refcnt, UNLIKELY, and verifyChecksum().

◆ tracksChecksum()

bool Cache::tracksChecksum ( const CachePage * page ) const

private

Definition at line 2577 of file Cache.cc.

◆ triggerChecksum()

void Cache::triggerChecksum ( uintptr_t key )

Triggers the cache to calculate the checksum of the given location. This may be useful to avoid a spurious writeback when reading data into a cache page for the first time.

Definition at line 2229 of file Cache.cc.

References calculateChecksum(), ensureUsable(), m_Lock, m_PageFilter, and m_Pages.

◆ trim()

size_t Cache::trim ( size_t count = 1 )

Attempts to trim the cache.

A trim is slightly different to a compact in that it is designed to be called in a non-emergency situation. This could be called, for example, after a process terminates, to clean up some old cached data while the system is already doing busywork. Or, it could be called when the system is idle to clean up a bit.

This will take the lock, also, unlike compact().

Definition at line 1608 of file Cache.cc.

References ensureUsable(), and lruEvict().

◆ unlinkPage()

void Cache::unlinkPage ( CachePage * pPage )

private

Unlink the given CachePage from the LRU list.

Definition at line 2542 of file Cache.cc.

References m_pLruHead, and Cache::CachePage::pNext.

Referenced by finishRetirement(), and promotePage().

Here is the caller graph for this function:

◆ updateWritebackIndex()

void Cache::updateWritebackIndex ( CachePage * page )

private

Definition at line 2587 of file Cache.cc.

◆ verifyChecksum()

bool Cache::verifyChecksum	(	CachePage *	pPage,
		bool	replace = `false`
	)

private

Verify the given CachePage's checksum.

Definition at line 2560 of file Cache.cc.

References Cache::CachePage::checkChecksum(), checksum(), Cache::CachePage::checksum, Cache::CachePage::checkZeroChecksum(), and Cache::CachePage::location.

Referenced by timer().

Here is the caller graph for this function:

◆ waitForPageEviction()

void Cache::waitForPageEviction ( uintptr_t key )

private

Waits until an in-progress same-key eviction has published its result.

Definition at line 713 of file Cache.cc.

References m_EvictionWaiters, m_Lock, m_PageFilter, and m_Pages.

Referenced by insert(), and insert().

Here is the caller graph for this function:

◆ writebackPage()

bool Cache::writebackPage	(	uintptr_t	key,
		uintptr_t	location,
		bool	wait
	)

private

Writes an already pinned page, optionally joining an active callback.

Definition at line 2043 of file Cache.cc.

References checksum(), Cache::CachePage::checksum, ProcessorBase::information(), Cache::CachePage::location, m_Callback, m_CallbackMeta, m_EvictionWaiters, m_Lock, and m_Pages.

Referenced by executeRequest(), and syncAll().

Here is the caller graph for this function:

Friends And Related Symbol Documentation

◆ CacheManager

friend class CacheManager

friend

Definition at line 208 of file Cache.h.

◆ CacheMemoryTestPeer

friend class CacheMemoryTestPeer

friend

Definition at line 209 of file Cache.h.

Member Data Documentation

◆ m_Allocator

MemoryAllocator Cache::m_Allocator

staticprivate

Static MemoryAllocator to allocate virtual address space for all caches.

Definition at line 763 of file Cache.h.

Referenced by finishRetirement(), insert(), and insert().

◆ m_AllocatorLock

Spinlock Cache::m_AllocatorLock

staticprivate

Lock for using the allocator.

Definition at line 766 of file Cache.h.

Referenced by finishRetirement(), insert(), and insert().

◆ m_BackgroundWriteback

writeback_batch_t Cache::m_BackgroundWriteback

private

Definition at line 786 of file Cache.h.

◆ m_bInCritical

Atomic<size_t> Cache::m_bInCritical

private

Are we currently in a critical section?

Definition at line 797 of file Cache.h.

Referenced by timer().

◆ m_Callback

writeback_t Cache::m_Callback

private

Callback to be called in the write-back timer handler.

Definition at line 785 of file Cache.h.

Referenced by evict(), retireWriteback(), setBackgroundWriteback(), setCallback(), sync(), syncAll(), timer(), and writebackPage().

◆ m_CallbackMeta

void* Cache::m_CallbackMeta

private

Metadata to pass to a callback.

Definition at line 794 of file Cache.h.

Referenced by evict(), executeRequest(), retireWriteback(), setCallback(), and writebackPage().

◆ m_DirtyTracking

DirtyTracking Cache::m_DirtyTracking

private

Definition at line 750 of file Cache.h.

◆ m_EvictionWaiters

WaitQueue Cache::m_EvictionWaiters

private

Coordinates forced drains with callbacks and outstanding page pins.

Definition at line 773 of file Cache.h.

Referenced by beginMutableLoan(), evict(), finishRetirement(), lookupStable(), prepareDiscardFrom(), read(), release(), retireWriteback(), syncAll(), waitForPageEviction(), Cache::PreparedDiscard::writeback(), and writebackPage().

◆ m_Lock

Spinlock Cache::m_Lock

private

Lock for this cache.

Definition at line 769 of file Cache.h.

Referenced by beginMutableLoan(), evict(), executeRequest(), exists(), finishRetirement(), insert(), insert(), lookup(), lookupStable(), lruEvict(), markDirty(), markEditing(), markExternallyWritable(), markNoLongerEditing(), pin(), prepareDiscardFrom(), read(), release(), retireWriteback(), setBackgroundWriteback(), setCallback(), setDirtyTracking(), sync(), syncAll(), timer(), triggerChecksum(), waitForPageEviction(), Cache::PreparedDiscard::writeback(), and writebackPage().

◆ m_ManagerId

uint64_t Cache::m_ManagerId

private

Stable identity assigned while registered with CacheManager.

Definition at line 780 of file Cache.h.

◆ m_ManagerOperations

OperationBarrier Cache::m_ManagerOperations

private

Drains manager callbacks before Cache storage is destroyed.

Definition at line 776 of file Cache.h.

Referenced by lookupStable(), prepareDiscardFrom(), and syncAll().

◆ m_ManagerTimerStamp

CacheManager::TimerStamp Cache::m_ManagerTimerStamp

private

Definition at line 781 of file Cache.h.

◆ m_Nanoseconds

uint64_t Cache::m_Nanoseconds

private

Timer interface: number of nanoseconds counted so far in the timer handler.

Definition at line 790 of file Cache.h.

Referenced by timer().

◆ m_PageConstraints

size_t Cache::m_PageConstraints

private

Constraints we need to apply to each page we allocate.

Definition at line 804 of file Cache.h.

Referenced by map().

◆ m_PageFilter

BloomFilter<uintptr_t> Cache::m_PageFilter

private

Bloom filter for lookups into m_Pages.

Definition at line 753 of file Cache.h.

Referenced by evict(), exists(), finishRetirement(), insert(), insert(), lookup(), lookupStable(), lruEvict(), markEditing(), markNoLongerEditing(), pin(), release(), retireWriteback(), sync(), triggerChecksum(), and waitForPageEviction().

◆ m_Pages

Tree<uintptr_t, CachePage*> Cache::m_Pages

private

Key-item pairs.

Definition at line 746 of file Cache.h.

Referenced by beginMutableLoan(), evict(), executeRequest(), exists(), finishRetirement(), insert(), insert(), lookup(), lookupStable(), lruEvict(), markDirty(), markEditing(), markExternallyWritable(), markNoLongerEditing(), pin(), prepareDiscardFrom(), read(), release(), retireWriteback(), setBackgroundWriteback(), setCallback(), setDirtyTracking(), sync(), syncAll(), timer(), triggerChecksum(), waitForPageEviction(), and writebackPage().

◆ m_PeriodicTimerEnabled

bool Cache::m_PeriodicTimerEnabled

private

Definition at line 782 of file Cache.h.

◆ m_pLruHead

CachePage* Cache::m_pLruHead

private

List of known CachePages, kept up-to-date with m_Pages but in LRU order.

Definition at line 758 of file Cache.h.

Referenced by linkPage(), lruEvict(), and unlinkPage().

◆ m_pLruTail

CachePage* Cache::m_pLruTail

private

Definition at line 759 of file Cache.h.

◆ m_ShutdownState

Atomic<size_t> Cache::m_ShutdownState

private

0 active, 1 shutting down, 2 drained, 3 terminal writeback failure, 4 deferred discard, 5 completing deferred discard.

Definition at line 801 of file Cache.h.

Referenced by ensureUsable(), prepareDiscardFrom(), release(), setBackgroundWriteback(), setCallback(), shutdown(), and syncAll().

◆ m_WritebackEpoch

uint64_t Cache::m_WritebackEpoch

private

Definition at line 791 of file Cache.h.

◆ m_WritebackPages

Tree<uintptr_t, CachePage*> Cache::m_WritebackPages

private

Explicit caches scan only dirty, unpublished, or externally writable pages.

Definition at line 749 of file Cache.h.

Referenced by finishRetirement(), syncAll(), and timer().

◆ MaxWritebackPages

constexpr size_t Cache::MaxWritebackPages = 64

staticconstexpr

Definition at line 514 of file Cache.h.

The documentation for this class was generated from the following files:

Classes

Public Types

Public Member Functions

Static Public Attributes

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ retirement_writeback_t

◆ writeback_batch_t

◆ writeback_t

Member Enumeration Documentation

◆ DirtyTracking

◆ DiscardStatus

◆ EvictionMode

◆ ShutdownMode

Constructor & Destructor Documentation

◆ Cache()

◆ ~Cache()

Member Function Documentation

◆ beginMutableLoan()

◆ calculateChecksum()

◆ checksum()

◆ discardEditing()

◆ discover_range()

◆ empty() [1/2]

◆ empty() [2/2]

◆ endAtomic()

◆ endMutableLoan()

◆ ensureUsable()

◆ evict() [1/2]

◆ evict() [2/2]

◆ executeRequest()

◆ exists()

◆ finishRetirement()

◆ insert() [1/2]

◆ insert() [2/2]

◆ linkPage()

◆ lookup()

◆ lookupStable()

◆ lruEvict()

◆ map()

◆ markDirty()

◆ markEditing()

◆ markExternallyWritable()

◆ markNoLongerEditing()

◆ needsPeriodicTimer()

◆ needsWriteback()

◆ pin()

◆ prepareDiscardFrom()

◆ promotePage()

◆ read()

◆ recordMutation()

◆ release()

◆ releaseBackgroundWriteback()

◆ releaseWriteback()

◆ retireWriteback()

◆ setBackgroundWriteback()

◆ setCallback()

◆ setDirtyTracking()

◆ shutdown()

◆ startAtomic()

◆ sync()

◆ syncAll() [1/2]

◆ syncAll() [2/2]

◆ syncBatch()

◆ syncBatchInternal()

◆ timer()

◆ tracksChecksum()

◆ triggerChecksum()

◆ trim()

◆ unlinkPage()

◆ updateWritebackIndex()

◆ verifyChecksum()

◆ waitForPageEviction()

◆ writebackPage()