/*
 * Copyright (c) 2020 Red Hat, Inc.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301, USA. 
 *
 * $Id: //eng/uds-releases/jasper/src/uds/pageCache.h#5 $
 */

#ifndef PAGE_CACHE_H
#define PAGE_CACHE_H

#include "atomicDefs.h"
#include "cacheCounters.h"
#include "chapterIndex.h"
#include "common.h"
#include "compiler.h"
#include "indexConfig.h"
#include "opaqueTypes.h"
#include "permassert.h"
#include "request.h"
#include "volumeStore.h"

typedef struct requestList {
  Request *first;
  Request *last;
} RequestList;

typedef struct cachedPage {
  /* whether this page is currently being read asynchronously */
  bool               cp_readPending;
  /* if equal to numCacheEntries, the page is invalid */
  unsigned int       cp_physicalPage;
  /* the value of the volume clock when this page was last used */
  int64_t            cp_lastUsed;
  /* the cache page data */
  struct volume_page cp_pageData;
  /* the chapter index page. This is here, even for record pages */
  DeltaIndexPage     cp_indexPage;
} CachedPage;

enum {
  VOLUME_CACHE_MAX_ENTRIES              = (UINT16_MAX >> 1),
  VOLUME_CACHE_QUEUED_FLAG              = (1 << 15),
  VOLUME_CACHE_DEFAULT_MAX_QUEUED_READS = 4096
};

typedef struct queuedRead {
  /* whether this queue entry is invalid */
  bool         invalid;
  /* whether this queue entry has a pending read on it */
  bool         reserved;
  /* physical page to read */
  unsigned int physicalPage;
  /* list of requests waiting on a queued read */
  RequestList  requestList;
} QueuedRead;

// Reason for invalidating a cache entry, used for gathering statistics
typedef enum invalidationReason {
  INVALIDATION_EVICT,           // cache is full, goodbye
  INVALIDATION_EXPIRE,          // your chapter is being overwritten
  INVALIDATION_ERROR,           // error happened; don't try to use data
  INVALIDATION_INIT_SHUTDOWN
} InvalidationReason;

/*
 * Value stored atomically in a SearchPendingCounter.  The low order 32 bits is
 * the physical page number of the cached page being read.  The high order 32
 * bits is a sequence number.
 *
 * An InvalidateCounter is only written by its zone thread by calling the
 * beginPendingSearch or endPendingSearch methods.
 *
 * Any other thread that is accessing an InvalidateCounter is reading the value
 * in the waitForPendingSearches method.
 */
typedef int64_t InvalidateCounter;
// Fields of InvalidateCounter.
// These must be 64 bit, so an enum cannot be not used.
#define PAGE_FIELD  ((long)UINT_MAX)   // The page number field
#define COUNTER_LSB (PAGE_FIELD + 1L)  // The LSB of the counter field

typedef struct __attribute__((aligned(CACHE_LINE_BYTES))) {
  atomic64_t atomicValue;
} SearchPendingCounter;

typedef struct pageCache {
  // Geometry governing the volume
  const Geometry *geometry;
  // The number of zones
  unsigned int    zoneCount;
  // The number of index entries
  unsigned int    numIndexEntries;
  // The max number of cached entries
  uint16_t        numCacheEntries;
  // The index used to quickly access page in cache - top bit is a 'queued'
  // flag
  uint16_t       *index;
  // The cache
  CachedPage     *cache;
  // A counter for each zone to keep track of when a search is occurring
  // within that zone.
  SearchPendingCounter *searchPendingCounters;
  // Queued reads, as a circular array, with first and last indexes
  QueuedRead     *readQueue;
  // Cache counters for stats.  This is the first field of a PageCache that is
  // not constant after the struct is initialized.
  CacheCounters   counters;
  /**
   * Entries are enqueued at readQueueLast.
   * To 'reserve' entries, we get the entry pointed to by readQueueLastRead
   * and increment last read.  This is done with a lock so if another reader
   * thread reserves a read, it will grab the next one.  After every read
   * is completed, the reader thread calls releaseReadQueueEntry which
   * increments readQueueFirst until it is equal to readQueueLastRead, but only
   * if the value pointed to by readQueueFirst is no longer pending.
   * This means that if n reads are outstanding, readQueueFirst may not
   * be incremented until the last of the reads finishes.
   *
   *  First                    Last
   * ||    |    |    |    |    |    ||
   *   LR   (1)   (2)
   *
   * Read thread 1 increments last read (1), then read thread 2 increments it
   * (2). When each read completes, it checks to see if it can increment first,
   * when all concurrent reads have completed, readQueueFirst should equal
   * readQueueLastRead.
   **/
  uint16_t              readQueueFirst;
  uint16_t              readQueueLastRead;
  uint16_t              readQueueLast;
  // The size of the read queue
  unsigned int          readQueueMaxSize;
  // Page access counter
  atomic64_t            clock;
} PageCache;

/**
 * Allocate a cache for a volume.
 *
 * @param geometry          The geometry governing the volume
 * @param chaptersInCache   The size (in chapters) of the page cache
 * @param readQueueMaxSize  The maximum size of the read queue
 * @param zoneCount         The number of zones in the index
 * @param cachePtr          A pointer to hold the new page cache
 *
 * @return UDS_SUCCESS or an error code
 **/
int makePageCache(const Geometry  *geometry,
                  unsigned int     chaptersInCache,
                  unsigned int     readQueueMaxSize,
                  unsigned int     zoneCount,
                  PageCache      **cachePtr)
  __attribute__((warn_unused_result));

/**
 * Clean up a volume's cache
 *
 * @param cache the volumecache
 **/
void freePageCache(PageCache *cache);

/**
 * Invalidates a page cache for a particular chapter
 *
 * @param cache           the page cache
 * @param chapter         the chapter
 * @param pagesPerChapter the number of pages per chapter
 * @param reason          the reason for invalidation
 *
 * @return UDS_SUCCESS or an error code
 **/
int invalidatePageCacheForChapter(PageCache          *cache,
                                  unsigned int        chapter,
                                  unsigned int        pagesPerChapter,
                                  InvalidationReason  reason)
  __attribute__((warn_unused_result));

/**
 * Find a page, invalidate it, and make its memory the least recent.  This
 * method is only exposed for the use of unit tests.
 *
 * @param cache        The cache containing the page
 * @param physicalPage The id of the page to invalidate
 * @param readQueue    The queue of pending reads (may be NULL)
 * @param reason       The reason for the invalidation, for stats
 * @param mustFind     If <code>true</code>, it is an error if the page
 *                     can't be found
 *
 * @return UDS_SUCCESS or an error code
 **/
int findInvalidateAndMakeLeastRecent(PageCache          *cache,
                                     unsigned int        physicalPage,
                                     QueuedRead         *readQueue,
                                     InvalidationReason  reason,
                                     bool                mustFind);

/**
 * Make the page the most recent in the cache
 *
 * @param cache   the page cache
 * @param pagePtr the page to make most recent
 *
 * @return UDS_SUCCESS or an error code
 **/
void makePageMostRecent(PageCache *cache, CachedPage *pagePtr);

/**
 * Verifies that a page is in the cache.  This method is only exposed for the
 * use of unit tests.
 *
 * @param cache the cache to verify
 * @param page the page to find
 *
 * @return UDS_SUCCESS or an error code
 **/
int assertPageInCache(PageCache *cache, CachedPage *page)
  __attribute__((warn_unused_result));

/**
 * Gets a page from the cache.
 *
 * @param [in] cache        the page cache
 * @param [in] physicalPage the page number
 * @param [in] probeType    the type of cache access being done (CacheProbeType
 *                          optionally OR'ed with CACHE_PROBE_IGNORE_FAILURE)
 * @param [out] pagePtr     the found page
 *
 * @return UDS_SUCCESS or an error code
 **/
int getPageFromCache(PageCache     *cache,
                     unsigned int   physicalPage,
                     int            probeType,
                     CachedPage   **pagePtr)
  __attribute__((warn_unused_result));

/**
 * Enqueue a read request
 *
 * @param cache        the page cache
 * @param request      the request that depends on the read
 * @param physicalPage the physicalPage for the request
 *
 * @return UDS_QUEUED  if the page was queued
 *         UDS_SUCCESS if the queue was full
 *         an error code if there was an error
 **/
int enqueueRead(PageCache *cache, Request *request, unsigned int physicalPage)
  __attribute__((warn_unused_result));

/**
 * Reserves a queued read for future dequeuing, but does not remove it from
 * the queue. Must call releaseReadQueueEntry to complete the process
 *
 * @param cache          the page cache
 * @param queuePos       the position in the read queue for this pending read
 * @param firstRequests  list of requests for the pending read
 * @param physicalPage   the physicalPage for the requests
 * @param invalid        whether or not this entry is invalid
 *
 * @return UDS_SUCCESS or an error code
 **/
bool reserveReadQueueEntry(PageCache     *cache,
                           unsigned int  *queuePos,
                           Request      **firstRequests,
                           unsigned int  *physicalPage,
                           bool          *invalid);

/**
 * Releases a read from the queue, allowing it to be reused by future
 * enqueues
 *
 * @param cache      the page cache
 * @param queuePos   queue entry position
 *
 * @return UDS_SUCCESS or an error code
 **/
void releaseReadQueueEntry(PageCache    *cache,
                           unsigned int  queuePos);

/**
 * Check for the page cache read queue being empty.
 *
 * @param cache  the page cache for which to check the read queue.
 *
 * @return  true if the read queue for cache is empty, false otherwise.
 **/
static INLINE bool readQueueIsEmpty(PageCache *cache)
{
  return (cache->readQueueFirst == cache->readQueueLast);
}

/**
 * Check for the page cache read queue being full.
 *
 * @param cache  the page cache for which to check the read queue.
 *
 * @return  true if the read queue for cache is full, false otherwise.
 **/
static INLINE bool readQueueIsFull(PageCache *cache)
{
  return (cache->readQueueFirst ==
    (cache->readQueueLast + 1) % cache->readQueueMaxSize);
}

/**
 * Selects a page in the cache to be used for a read.
 *
 * This will clear the pointer in the page map and
 * set readPending to true on the cache page
 *
 * @param cache          the page cache
 * @param pagePtr        the page to add
 *
 * @return UDS_SUCCESS or an error code
 **/
int selectVictimInCache(PageCache     *cache,
                        CachedPage   **pagePtr)
  __attribute__((warn_unused_result));

/**
 * Completes an async page read in the cache, so that
 * the page can now be used for incoming requests.
 *
 * This will invalidate the old cache entry and point
 * the page map for the new page to this entry
 *
 * @param cache          the page cache
 * @param physicalPage   the page number
 * @param page           the page to complete processing on
 *
 * @return UDS_SUCCESS or an error code
 **/
int putPageInCache(PageCache    *cache,
                   unsigned int  physicalPage,
                   CachedPage   *page)
  __attribute__((warn_unused_result));

/**
 * Cancels an async page read in the cache, so that
 * the page can now be used for incoming requests.
 *
 * This will invalidate the old cache entry and clear
 * the read queued flag on the page map entry, if it
 * was set.
 *
 * @param cache          the page cache
 * @param physicalPage   the page number to clear the queued read flag on
 * @param page           the page to cancel processing on
 *
 * @return UDS_SUCCESS or an error code
 **/
void cancelPageInCache(PageCache    *cache,
                       unsigned int  physicalPage,
                       CachedPage   *page);

/**
 * Get the page cache size
 *
 * @param cache the page cache
 *
 * @return the size of the page cache
 **/
size_t getPageCacheSize(PageCache *cache)
  __attribute__((warn_unused_result));


/**
 * Read the InvalidateCounter for the given zone.
 *
 * @param cache       the page cache
 * @param zoneNumber  the zone number
 *
 * @return the InvalidateCounter value
 **/
static INLINE InvalidateCounter getInvalidateCounter(PageCache    *cache,
                                                     unsigned int  zoneNumber)
{
  return atomic64_read(&cache->searchPendingCounters[zoneNumber].atomicValue);
}

/**
 * Write the InvalidateCounter for the given zone.
 *
 * @param cache              the page cache
 * @param zoneNumber         the zone number
 * @param invalidateCounter  the InvalidateCounter value to write
 **/
static INLINE void setInvalidateCounter(PageCache         *cache,
                                        unsigned int       zoneNumber,
                                        InvalidateCounter  invalidateCounter)
{
  atomic64_set(&cache->searchPendingCounters[zoneNumber].atomicValue,
               invalidateCounter);
}

/**
 * Return the physical page number of the page being searched.  The return
 * value is only valid if searchPending indicates that a search is in progress.
 *
 * @param counter  the InvalidateCounter value to check
 *
 * @return the page that the zone is searching
 **/
static INLINE unsigned int pageBeingSearched(InvalidateCounter counter)
{
  return counter & PAGE_FIELD;
}

/**
 * Determines whether a given value indicates that a search is occuring.
 *
 * @param invalidateCounter  the InvalidateCounter value to check
 *
 * @return true if a search is pending, false otherwise
 **/
static INLINE bool searchPending(InvalidateCounter invalidateCounter)
{
  return (invalidateCounter & COUNTER_LSB) != 0;
}

/**
 * Determines whether there is a search occuring for the given zone.
 *
 * @param cache       the page cache
 * @param zoneNumber  the zone number
 *
 * @return true if a search is pending, false otherwise
 **/
static INLINE bool isSearchPending(PageCache    *cache,
                                   unsigned int  zoneNumber)
{
  return searchPending(getInvalidateCounter(cache, zoneNumber));
}

/**
 * Increment the counter for the specified zone to signal that a search has
 * begun.  Also set which page is being searched.  The searchPendingCounters
 * are protecting read access to pages indexed by the cache.  This is the
 * "lock" action.
 *
 * @param cache         the page cache
 * @param physicalPage  the page that the zone is searching
 * @param zoneNumber    the zone number
 **/
static INLINE void beginPendingSearch(PageCache    *cache,
                                      unsigned int  physicalPage,
                                      unsigned int  zoneNumber)
{
  InvalidateCounter invalidateCounter = getInvalidateCounter(cache,
                                                             zoneNumber);
  invalidateCounter &= ~PAGE_FIELD;
  invalidateCounter |= physicalPage;
  invalidateCounter += COUNTER_LSB;
  setInvalidateCounter(cache, zoneNumber, invalidateCounter);
  ASSERT_LOG_ONLY(searchPending(invalidateCounter),
                  "Search is pending for zone %u", zoneNumber);
  /*
   * This memory barrier ensures that the write to the invalidate counter is
   * seen by other threads before this threads accesses the cached page.  The
   * corresponding read memory barrier is in waitForPendingSearches.
   */
  smp_mb();
}

/**
 * Increment the counter for the specified zone to signal that a search has
 * finished.  We do not need to reset the page since we only should ever look
 * at the page value if the counter indicates a search is ongoing.  The
 * searchPendingCounters are protecting read access to pages indexed by the
 * cache.  This is the "unlock" action.
 *
 * @param cache       the page cache
 * @param zoneNumber  the zone number
 **/
static INLINE void endPendingSearch(PageCache    *cache,
                                    unsigned int  zoneNumber)
{
  // This memory barrier ensures that this thread completes reads of the
  // cached page before other threads see the write to the invalidate counter.
  smp_mb();

  InvalidateCounter invalidateCounter = getInvalidateCounter(cache,
                                                             zoneNumber);
  ASSERT_LOG_ONLY(searchPending(invalidateCounter),
                  "Search is pending for zone %u", zoneNumber);
  invalidateCounter += COUNTER_LSB;
  setInvalidateCounter(cache, zoneNumber, invalidateCounter);
}

#endif /* PAGE_CACHE_H */