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/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/RequestQueue.h"
#include "pedigree/kernel/utilities/Tree.h"
#include "pedigree/kernel/utilities/new"

class Thread;
class UnlikelyLock;

#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 CacheManager :
#ifndef STANDALONE_CACHE
    public TimerHandler,
#endif
    public RequestQueue
{
  public:
    CacheManager();
    virtual ~CacheManager();

    static CacheManager &instance()
    {
        return m_Instance;
    }

    void initialise();

    void registerCache(Cache *pCache);
    void unregisterCache(Cache *pCache);

    bool trimAll(size_t count = 1);

    virtual void timer(uint64_t delta, InterruptState &state);

#ifdef THREADS
    void trimThread();
#endif

  private:
    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 bool compareRequests(const Request &a, const Request &b)
    {
        // p2 = CallbackCause, p3 = key in m_Pages
        return (a.p2 == b.p2) && (a.p3 == b.p3);
    }

    static CacheManager m_Instance;

    List<Cache *> m_Caches;

#ifdef THREADS
    Thread *m_pTrimThread;
#endif

    bool m_bActive;
};

class EXPORTED_PUBLIC Cache
{
  private:
    struct CachePage
    {
        uintptr_t key;

        uintptr_t location;

        size_t refcnt;

        uint64_t checksum[2];

        bool checksumChanging;

        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 void (*writeback_t)(
        CacheConstants::CallbackCause cause, uintptr_t loc, uintptr_t page,
        void *meta);

    Cache(size_t pageConstraints = 0);
    virtual ~Cache();

    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()
    {
        m_bInCritical = 1;
    }

    void endAtomic()
    {
        m_bInCritical = 0;
    }

    void markEditing(uintptr_t key, size_t length = 0);

    void markNoLongerEditing(uintptr_t key, size_t length = 0);

  private:
    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]);

    struct callbackMeta
    {
        CacheConstants::CallbackCause cause;
        writeback_t callback;
        uintptr_t loc;
        uintptr_t page;
        void *meta;
        UnlikelyLock *cacheLock;
    };

  public:
    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:
    Tree<uintptr_t, CachePage *> m_Pages;

    BloomFilter<uintptr_t> m_PageFilter;

    CachePage *m_pLruHead;
    CachePage *m_pLruTail;

    static MemoryAllocator m_Allocator;

    static Spinlock m_AllocatorLock;

    Spinlock m_Lock;

    writeback_t m_Callback;

    uint64_t m_Nanoseconds;

    void *m_CallbackMeta;

    Atomic<size_t> m_bInCritical;

    size_t m_PageConstraints;

#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