Cache.h

/*
 * Copyright (c) 2008-2014, Pedigree Developers
 *
 * Please see the CONTRIB file in the root of the source tree for a full
 * list of contributors.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
 
#ifndef CACHE_H
#define CACHE_H
#include "pedigree/kernel/Atomic.h"
#include "pedigree/kernel/Spinlock.h"
#include "pedigree/kernel/compiler.h"
#include "pedigree/kernel/machine/TimerHandler.h"
#include "pedigree/kernel/process/Mutex.h"
#include "pedigree/kernel/process/OperationBarrier.h"
#include "pedigree/kernel/process/TerminationDeferral.h"
#include "pedigree/kernel/processor/state_forward.h"
#include "pedigree/kernel/processor/types.h"
#include "pedigree/kernel/utilities/BloomFilter.h"
#include "pedigree/kernel/utilities/CacheConstants.h"
#include "pedigree/kernel/utilities/List.h"
#include "pedigree/kernel/utilities/MemoryAllocator.h"
#include "pedigree/kernel/utilities/Pointers.h"
#include "pedigree/kernel/utilities/RequestQueue.h"
#include "pedigree/kernel/utilities/Tree.h"
#include "pedigree/kernel/utilities/new"
#include "pedigree/kernel/utilities/utility.h"
 
#include <config.h>
 
class Thread;
class Timer;
class UnlikelyLock;
 
#ifndef STANDALONE_CACHE
#define STANDALONE_CACHE 0
#endif
 
#define CACHE_AGE_THRESHOLD 10
 
#define CACHE_NUM_THRESHOLD 2
 
#define CACHE_WRITEBACK_PERIOD 500
 
// Forward declaration of Cache so CacheManager can be defined first
class Cache;
 
class EXPORTED_PUBLIC CacheManager :
#if !STANDALONE_CACHE
    public TimerHandler,
#endif
    public RequestQueue {
  friend class Cache;
  friend class CacheManagerTestPeer;
 
 public:
  CacheManager();
  virtual ~CacheManager();
 
  static CacheManager& instance() {
    if (!m_Instance) {
      m_Instance = new CacheManager;
    }
    return *m_Instance;
  }
 
  static void destroyInstance() {
    delete m_Instance;
    m_Instance = nullptr;
  }
 
  void initialise();
 
  MUST_USE_RESULT bool shutdown();
 
  void registerCache(Cache* pCache);
  void unregisterCache(Cache* pCache);
 
  bool trimAll(size_t count = 1);
 
  virtual void timer(uint64_t delta);
 
#if THREADS
  void trimThread();
#endif
 
 private:
  void stopPeriodicWork();
  void timerTick(uint64_t delta, bool memoryPressure);
 
  struct TimerStamp {
    uint64_t elapsed = 0;
    uint64_t wraps = 0;
 
    void advance(uint64_t delta);
    uint64_t since(const TimerStamp& previous) const;
  };
 
  bool findNextCache(uint64_t afterId, uint64_t maximumId, Cache*& cache, uint64_t& cacheId,
                     bool timersOnly = false);
  bool takeTimerStamp(TimerStamp& stamp);
  void dispatchTimer(Cache* cache, const TimerStamp& stamp);
 
#if THREADS
  struct CacheRequest {
    CacheRequest(Cache* requestCache, OperationBarrier::Lease&& requestLease)
        : cache(requestCache), lease(pedigree_std::move(requestLease)) {}
 
    Cache* cache;
    OperationBarrier::Lease lease;
  };
 
  bool callbackContext() const {
    return callbackActiveOnCurrentThread();
  }
 
  bool acquireCache(Cache* cache, uint64_t& generation, OperationBarrier::Lease& lease);
 
  bool acquireNextCache(uint64_t afterId, uint64_t maximumId, Cache*& cache, uint64_t& cacheId,
                        OperationBarrier::Lease& lease, bool timersOnly = false);
 
  uint64_t cacheGenerationWatermark();
#endif
 
  uint64_t addCacheRequest(Cache* cache, bool asynchronous, CacheConstants::CallbackCause cause,
                           uintptr_t key, uintptr_t location = 0, bool transferredPin = false,
                           bool batch = false);
 
  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);
  virtual void cancelRequest(const Request& request);
 
  virtual bool compareRequests(const Request& a, const Request& b) {
    // p1 = Cache, p2 = CallbackCause, p3 = key in m_Pages.
    return (a.p1 == b.p1) && (a.p2 == b.p2) && (a.p3 == b.p3) && (a.p6 == b.p6);
  }
 
  static CacheManager* m_Instance;
 
  Tree<uint64_t, Cache*> m_Caches;
 
  uint64_t m_NextCacheId;
  TimerStamp m_TimerClock;
  uint64_t m_TrimDelta;
 
#if THREADS
  Mutex m_CachesLock;
 
  Thread* m_pTrimThread;
  WaitQueue m_TrimWaiters;
  bool m_bTrimRequested;
#endif
 
  bool m_bActive;
 
  Timer* m_pTimer;
  Atomic<size_t> m_TerminalState;
};
 
class EXPORTED_PUBLIC Cache {
  friend class CacheManager;
  friend class CacheMemoryTestPeer;
 
 private:
  struct CachePage {
    uintptr_t key;
 
    uintptr_t location;
 
    size_t refcnt;
    size_t writebackPins;
    size_t mutableLoans;
    bool directWriteback;
 
    bool callbackActive;
#if THREADS
    Thread* callbackOwner;
#endif
 
    enum class EvictionState {
      None,
      WriteBack,
      Draining,
      Retiring,
    } evictionState;
 
    uint64_t checksum[2];
 
    bool checksumChanging;
 
    bool writebackFailed;
    bool externallyWritable;
    bool writebackIndexed;
    uint64_t mutationGeneration;
    uint64_t writtenGeneration;
    uint64_t writebackEpoch;
 
    enum Status {
      // The page is being edited and should not be considered for any
      // writeback operation.
      Editing,
      // The page has been marked as no longer being edited and should
      // only have a checksum calculated, but no writeback.
      EditTransition,
      // The checksum is in flux.
      ChecksumChanging,
      // The checksum was in flux but is now stable. A transition into
      // this state will trigger a writeback.
      ChecksumStable
    } status;
 
    CachePage* pNext;
    CachePage* pPrev;
 
    bool checkChecksum(uint64_t other[2]) const;
 
    bool checkZeroChecksum() const;
  };
 
 public:
  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);
 
#if HOSTED && PEDIGREE_HOSTED_SMOKE_TESTS
  typedef void (*writeback_admission_hook_t)(Cache* cache, uintptr_t key, void* meta);
#endif
 
  Cache(size_t pageConstraints = 0);
  virtual ~Cache();
 
  enum class ShutdownMode { WriteBack, Discard, DiscardDeferred };
 
  bool shutdown(ShutdownMode mode = ShutdownMode::WriteBack);
 
  void setCallback(writeback_t newCallback, void* meta);
 
  enum class DirtyTracking { Checksum, Explicit };
 
  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);
 
#if HOSTED && PEDIGREE_HOSTED_SMOKE_TESTS
  void setWritebackAdmissionHookForTest(writeback_admission_hook_t hook, void* meta);
#endif
 
  bool empty();
 
  struct DiscardReference {
    uintptr_t key;
    size_t references;
  };
  enum class DiscardStatus { Ready, NoMemory, Busy, Invalid, Closed };
 
  class EXPORTED_PUBLIC PreparedDiscard {
   public:
    ~PreparedDiscard();
    MUST_USE_RESULT bool writeback(retirement_writeback_t callback, void* context);
    void commit();
 
   private:
    friend class Cache;
    struct Entry;
    explicit PreparedDiscard(Cache& cache);
    NOT_COPYABLE_OR_ASSIGNABLE(PreparedDiscard);
    TerminationDeferral m_TerminationDeferral;
    Cache& m_Cache;
    UniqueArray<Entry> m_Entries;
    size_t m_Count;
    bool m_Committed;
#if THREADS
    OperationBarrier::Lease m_Lease;
#endif
  };
 
  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();
 
  static constexpr size_t MaxWritebackPages = 64;
  struct WritebackPage {
    uintptr_t key;
    uintptr_t location;
  };
  class DirectWritebackLease {
   public:
    DirectWritebackLease() : m_Cache(nullptr), m_Page(nullptr), m_Physical(0) {}
    ~DirectWritebackLease() {
      release();
    }
    DirectWritebackLease(const DirectWritebackLease&) = delete;
    DirectWritebackLease& operator=(const DirectWritebackLease&) = delete;
 
    bool acquire(Cache& cache, uintptr_t key, uintptr_t location);
    void release();
    physical_uintptr_t physical() const {
      return m_Physical;
    }
 
   private:
    Cache* m_Cache;
    CachePage* m_Page;
    physical_uintptr_t m_Physical;
  };
  using writeback_batch_t = bool (*)(const WritebackPage*, size_t, void*);
  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() {
    if (!ensureUsable("startAtomic")) {
      return;
    }
    m_bInCritical = 1;
  }
 
  void endAtomic() {
    if (!ensureUsable("endAtomic")) {
      return;
    }
    m_bInCritical = 0;
  }
 
  void markEditing(uintptr_t key, size_t length = 0);
 
  void markNoLongerEditing(uintptr_t key, size_t length = 0);
 
 private:
  enum class EvictionMode {
    Ordinary,
    DiscardBaseReference,
    DiscardEditing,
    DiscardDirty,
  };
 
  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]);
 
  struct callbackMeta {
    CacheConstants::CallbackCause cause;
    writeback_t callback;
    uintptr_t loc;
    uintptr_t page;
    void* meta;
    UnlikelyLock* cacheLock;
  };
 
 public:
  virtual bool needsPeriodicTimer() const {
    return __atomic_load_n(&m_PeriodicTimerEnabled, __ATOMIC_ACQUIRE);
  }
 
  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);
 
 private:
  struct BackgroundWriteback {
    size_t count = 0;
    uintptr_t keys[MaxWritebackPages];
  };
  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);
 
  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;
 
  static MemoryAllocator m_Allocator;
 
  static Spinlock m_AllocatorLock;
 
  Spinlock m_Lock;
 
#if THREADS
  WaitQueue m_EvictionWaiters;
 
  OperationBarrier m_ManagerOperations;
#endif
 
  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;
 
#if HOSTED && PEDIGREE_HOSTED_SMOKE_TESTS
  writeback_admission_hook_t m_WritebackAdmissionHook;
  void* m_WritebackAdmissionHookMeta;
#endif
 
#ifdef STANDALONE_CACHE
  static void discover_range(uintptr_t& start, uintptr_t& end);
#endif
};
 
class EXPORTED_PUBLIC CachePageGuard {
 public:
  CachePageGuard(Cache& cache, uintptr_t location);
  virtual ~CachePageGuard();
 
 private:
  Cache& m_Cache;
  uintptr_t m_Location;
};
 
#endif