#include <Cache.h>

Collaboration diagram for Cache:

Classes
struct	CachePage

struct	callbackMeta

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

Public Member Functions
	Cache (size_t pageConstraints=0)

void	setCallback (writeback_t newCallback, void *meta)

uintptr_t	lookup (uintptr_t key)

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)

void	empty ()

void	release (uintptr_t key)

bool	pin (uintptr_t key)

size_t	trim (size_t count=1)

void	sync (uintptr_t key, bool async)

void	triggerChecksum (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 void	timer (uint64_t delta, InterruptState &state)

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)

Private Member Functions
bool	map (uintptr_t virt) const

bool	evict (uintptr_t key, bool bLock, bool bPhysicalLock, bool bRemove)

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)

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

Private Attributes
Tree< uintptr_t, CachePage * >	m_Pages

BloomFilter< uintptr_t >	m_PageFilter

CachePage *	m_pLruHead

CachePage *	m_pLruTail

Spinlock	m_Lock

writeback_t	m_Callback

uint64_t	m_Nanoseconds

void *	m_CallbackMeta

Atomic< size_t >	m_bInCritical

size_t	m_PageConstraints

Static Private Attributes
static MemoryAllocator	m_Allocator

static Spinlock	m_AllocatorLock

Detailed Description

Provides an abstraction of a data cache.

Definition at line 118 of file Cache.h.

Member Typedef Documentation

typedef void(* 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.

Then, the write-back thread will mark the page as not-dirty.

Definition at line 177 of file Cache.h.

Member Function Documentation

void Cache::calculateChecksum ( CachePage * pPage )

private

Calculate a checksum for the given CachePage.

Definition at line 855 of file Cache.cc.

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

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

private

Checksum do-er.

Definition at line 879 of file Cache.cc.

void Cache::empty ( )

Empties the cache.

Will not respect refcounts.

Definition at line 460 of file Cache.cc.

References Process::m_Lock, and Cache::CachePage::refcnt.

void Cache::endAtomic ( )

inline

Leaves the critical section for this cache.

Definition at line 291 of file Cache.h.

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 455 of file Cache.cc.

bool Cache::evict	(	uintptr_t	key,
		bool	bLock,
		bool	bPhysicalLock,
		bool	bRemove
	)

private

evict doer

Definition at line 477 of file Cache.cc.

References Spinlock::acquire(), PhysicalMemoryManager::freePage(), VirtualAddressSpace::getMapping(), Processor::information(), PhysicalMemoryManager::instance(), Cache::CachePage::location, Process::m_Lock, NOTICE, Cache::CachePage::refcnt, Spinlock::release(), and VirtualAddressSpace::unmap().

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 765 of file Cache.cc.

References NOTICE.

Referenced by CacheManager::executeRequest().

Here is the caller graph for this function:

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

Checks if the entire range specified exists in the cache.

Definition at line 431 of file Cache.cc.

References Process::m_Lock.

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.

Parameters

alreadyExisted can be used to find out if the return value is a page that already existed, and no mapping was completed. This can be used to do an 'insert or get' operation atomically.

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

Definition at line 258 of file Cache.cc.

References Cache::CachePage::checksum, FATAL, Cache::CachePage::key, Cache::CachePage::location, Process::m_Lock, and Cache::CachePage::refcnt.

Referenced by DiskImage::read(), FatFile::readBlock(), and File::readIntoCache().

Here is the caller graph for this function:

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.

Parameters

alreadyExisted can be used to find out if the return value is a page that already existed, and no mapping was completed. This can be used to do an 'insert or get' operation atomically.

Todo:: no - this doesn't check the full size!

Definition at line 329 of file Cache.cc.

References Cache::CachePage::checksum, Dec, ERROR, FATAL, Hex, Cache::CachePage::key, Cache::CachePage::location, Process::m_Lock, Cache::CachePage::refcnt, and WARNING.

void Cache::linkPage ( CachePage * pPage )

private

Link the given CachePage to the LRU list.

Definition at line 826 of file Cache.cc.

References Cache::CachePage::pNext.

uintptr_t Cache::lookup ( uintptr_t key )

Looks for key , increasing refcnt by one if returned.

Definition at line 235 of file Cache.cc.

References Cache::CachePage::location, Process::m_Lock, and Cache::CachePage::refcnt.

Referenced by File::getPhysicalPage(), and DiskImage::read().

Here is the caller graph for this function:

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 799 of file Cache.cc.

References PhysicalMemoryManager::instance(), and Cache::CachePage::key.

bool Cache::map ( uintptr_t virt ) const

private

mapping doer

Definition at line 417 of file Cache.cc.

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

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.

Definition at line 884 of file Cache.cc.

References Process::m_Lock, and WARNING.

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

Mark the given page as no longer being edited.

Definition at line 919 of file Cache.cc.

References Process::m_Lock, and WARNING.

Referenced by DiskImage::read(), FatFile::readBlock(), and File::readIntoCache().

Here is the caller graph for this function:

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 557 of file Cache.cc.

References Process::m_Lock, and Cache::CachePage::refcnt.

Referenced by File::getPhysicalPage(), DiskImage::pin(), and FatFile::pinBlock().

Here is the caller graph for this function:

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 837 of file Cache.cc.

void Cache::release ( uintptr_t key )

Decreases key 's refcnt by one.

Definition at line 578 of file Cache.cc.

References RequestQueue::addAsyncRequest(), assert, Process::m_Lock, and Cache::CachePage::refcnt.

Referenced by File::returnPhysicalPage(), DiskImage::unpin(), and FatFile::unpinBlock().

Here is the caller graph for this function:

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

Set the write back callback to the given function.

Definition at line 759 of file Cache.cc.

Referenced by FatFile::FatFile().

Here is the caller graph for this function:

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 283 of file Cache.h.

void 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.

Definition at line 625 of file Cache.cc.

References RequestQueue::addAsyncRequest(), RequestQueue::addRequest(), Cache::CachePage::location, Process::m_Lock, and WARNING.

Referenced by FatFile::sync().

Here is the caller graph for this function:

void Cache::timer	(	uint64_t	delta,
		InterruptState &	state
	)

virtual

Cache timer handler.

Will call callbacks as needed to write dirty pages back to the backing store. If no callback is set for the Cache instance, the timer will not fire.

Todo:: something with locks

Definition at line 682 of file Cache.cc.

References RequestQueue::addAsyncRequest(), ERROR, Hex, LIKELY, Cache::CachePage::location, NOTICE, and UNLIKELY.

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 664 of file Cache.cc.

References Process::m_Lock.

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 606 of file Cache.cc.

References Process::m_Lock.

void Cache::unlinkPage ( CachePage * pPage )

private

Unlink the given CachePage from the LRU list.

Definition at line 843 of file Cache.cc.

References Cache::CachePage::pNext.

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

private

Verify the given CachePage's checksum.

Definition at line 861 of file Cache.cc.

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

Member Data Documentation

MemoryAllocator Cache::m_Allocator

staticprivate

Static MemoryAllocator to allocate virtual address space for all caches.

Definition at line 403 of file Cache.h.

Spinlock Cache::m_AllocatorLock

staticprivate

Lock for using the allocator.

Definition at line 406 of file Cache.h.

Atomic<size_t> Cache::m_bInCritical

private

Are we currently in a critical section?

Definition at line 422 of file Cache.h.

writeback_t Cache::m_Callback

private

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

Definition at line 412 of file Cache.h.

void* Cache::m_CallbackMeta

private

Metadata to pass to a callback.

Definition at line 419 of file Cache.h.

Spinlock Cache::m_Lock

private

Lock for this cache.

Definition at line 409 of file Cache.h.

uint64_t Cache::m_Nanoseconds

private

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

Definition at line 416 of file Cache.h.

size_t Cache::m_PageConstraints

private

Constraints we need to apply to each page we allocate.

Definition at line 425 of file Cache.h.

BloomFilter<uintptr_t> Cache::m_PageFilter

private

Bloom filter for lookups into m_Pages.

Definition at line 393 of file Cache.h.

Tree<uintptr_t, CachePage *> Cache::m_Pages

private

Key-item pairs.

Definition at line 390 of file Cache.h.

CachePage* Cache::m_pLruHead

private

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

Definition at line 398 of file Cache.h.

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

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

Member Function Documentation

Member Data Documentation