//
// Copyright (c) Microsoft Corporation.  All rights reserved.
//
//
// This source code is licensed under Microsoft Shared Source License
// Version 1.0 for Windows CE.
// For a copy of the license visit http://go.microsoft.com/fwlink/?LinkId=3223.
//
/*++


Module Name:

    buffer.c

Abstract:

    This file contains routines for managing disk data buffers.  A
    buffer is one or more contiguous blocks.  Blocks are a fixed
    (compile-time) size, independent of sector size.  Buffer size is
    dynamic however; it is calculated as the LARGER of the sector size
    and the block size, and there MUST be an integral number of both
    blocks AND sectors per buffer (and normally it's the SAME integral
    number, because our fixed block size is normally the same as
    the sector size of most media -- 512 bytes).

    All read/write access to a volume is through the buffers managed
    by this module.  Every buffer has a variety of states:  it may be
    VALID or INVALID, HELD or UNHELD, DIRTY or CLEAN, and ASSIGNED or
    UNASSIGNED.

    VALID means the buffer contains data for some block on some volume;
    INVALID means it doesn't contain anything yet (or anymore, if a
    dirty buffer couldn't be committed due to some disk error).  A buffer
    is valid if its pvol points to a VOLUME structure and is invalid if
    null.

    HELD means the buffer is currently being examined and/or modified
    by one or more threads; UNHELD means it isn't.  Unless a buffer
    size was chosen that spans multiple sectors (and therefore multiple
    streams), it will be rare for a buffer to be held by more than one
    thread, because buffers are normally accessed only on behalf of streams,
    and streams are normally accessed only while their critical section
    is owned.

    DIRTY means a buffer contains changes that need to be written to
    a volume;  CLEAN means it matches the volume.  There is no lazy-write
    mechanism currently, so when a function is done modifying buffers, it
    needs to commit those dirty buffers synchronously.  CommitBuffer does
    this by clearing a buffer's DIRTY bit and then writing the buffer's
    data to disk;  thus, if another thread dirties the same buffer before
    the write completes, the buffer remains dirty.  Because a DIRTY buffer
    is not necessarily a HELD buffer, CommitBuffer also holds a buffer
    across the entire "cleaning" operation to insure that FindBuffer
    doesn't steal the buffer until it's fully committed.  In summary, a
    buffer must always be HELD while its DIRTY/CLEAN state is being changed.

    ASSIGNED means a buffer is assigned to some stream.  We assign
    buffers to streams so that when CommitStreamBuffers is called, we
    can readily find all the buffers containing data for that stream.
    Note that since the buffer size could be such that multiple streams
    could share the same buffers, we force AssignStreamBuffer to commit
    a buffer before giving it to a different stream.  This may or may
    not result in an extra write, but at least it preserves the notion
    that once CommitStreamBuffers has completed, the stream is fully
    committed.

    Streams also have the notion of a CURRENT buffer.  When they call
    ReadStreamBuffer, whatever buffer supplies the data is HELD and then
    recorded in the stream as the stream's current buffer (s_pbufCur).
    If a subsequent ReadStreamBuffer returns the same buffer, it remains
    the current buffer;  if it returns a different buffer, the previous
    current buffer is unheld and no longer current.

    A stream's current buffer state is protected by the stream's
    critical section;  ie, another thread cannot seek to another part of
    some stream, thereby forcing another buffer to become current, while
    an earlier thread was still examining data in an earlier current
    buffer.  A problem, however, can arise on the SAME thread.  MoveFile
    is a good example:  if MoveFile tries to open two streams at once
    (one for the source filename and one for destination) and both
    source and destination happen to be the same directory (ie, the same
    stream), MoveFile will simply get two pointers to the SAME stream
    data structure;  thus, every time it seeks and reads something using
    one stream, it could be modifying the stream's current buffer and
    thereby invalidating any pointer(s) it obtained via the other stream.

    So MoveFile, and any other code that juggles multiple streams, needs
    to be sure that its streams are unique, or take care to explicitly
    hold a stream's current buffer before operating on a second, potentially
    identical stream.

    Furthermore, every function that juggles multiple streams probably
    also uses multiple buffers.  Even if we had N buffers in the buffer
    pool (where N is a large number), we could have N threads all arrive
    in MoveFile at the same time, all obtain their first buffer, and then
    all block trying to get a second buffer.  Ouch.

    The easiest way to solve that problem is to count buffer-consuming
    threads in FATFS, and when the number of threads * MIN_BUFFERS exceeds
    the number of available buffers, block until available buffers increases
    sufficiently.

Revision History:

    Lazy Writer Thread (added post v2.0 -JTP)

    Initial design goals for lazy writing include:

        1. Simplicity.  Create a dedicated lazy-writer thread when FATFS.DLL
        is loaded and initialized for the first time.  The natural place
        to manage creation/destruction of the thread is entirely within the
        BufInit and BufDeinit functions.

        Although it might be nice to have "lazy lazy-writer thread creation"
        (ie, to defer thread creation until we get to a point where something
        has actually been written), I think that for now WE will be the
        lazy ones, and defer that feature to a later date.  Besides, we reduce
        the risk of running into some architectural problem with that approach
        downstream.

        2. Minimum lazy-writer wake-ups (ie, it shouldn't wake up if there's
        no work to do), balanced by a maximum age for dirty data.  Age will be
        tracked by timestamps in the buffer headers, updating those timestamps
        every time DirtyBuffer is called.

        3. Maximum transparency (ie, existing FATFS code shouldn't change too
        much).  However, we do need to more carefully differentiate between
        those places where we really need to COMMIT as opposed to simply WRITE.
        Thus, we now have WriteStreamBuffers and WriteAndReleaseStreamBuffers to
        complement CommitStreamBuffers and CommitAndReleaseStreamBuffers.
--*/

#include "fatfs.h"


/*  The minimum number of buffers is the number of buffers that may be
 *  simultaneously held during any one operation.  For example, when
 *  CreateName is creating an entry for a new subdirectory, it can have
 *  holds on 1 FAT buffer and up to 2 directory buffers (in the case of
 *  zeroing a growing directory), all simultaneously.  We round the minimum
 *  up to 4, (a) to be safe, and (b) to evenly divide the default number of
 *  buffers.
 */

#define MIN_BUFFERS     4
#define DEF_BUFFERS     32      
#if (DEF_BUFFERS < MIN_BUFFERS)
#error  Default buffer pool size too small
#endif

#if (DEF_BUFFERS % MIN_BUFFERS)
#error  Default buffer pool size should be multiple of minimum
#endif

#if ((DEF_BUFFERS*512) & (4096-1))
#error  Default buffer pool memory allocation should be multiple of typical page size
#endif




//#define BIG_BUFFERS

DWORD       cbBuf;              // buffer size (computed at run-time)
DWORD       cbufTotal;          // total number of buffers
DWORD       cbufError;          // total buffers with outstanding write errors


DWORD       flBuf;              // see GBUF_*
#define GBUF_LOCALALLOC         0x00000001

DWORD       cblkBuf;            // blocks per buffer (computed at run-time)
DWORD       maskBufBlock;       // to convert blocks to buffer-granular blocks
PBYTE       pbBufCarve;         // address of carved buffer memory, if any
BUF_DLINK   dlBufMRU;           // MRU list of buffers
DWORD       cBufVolumes;        // number of volumes using buffer pool
DWORD       cBufThreads;        // number of threads buffer pool can handle
DWORD       cBufThreadsOrig;    // number of threads buffer pool can handle
HANDLE      hevBufThreads;      // auto-reset event signalled when another thread can be handled
CRITICAL_SECTION csBuffers;     // buffer pool critical section




BOOL BufInit(void)
{
    InitializeCriticalSection(&csBuffers);
    DEBUGALLOC(DEBUGALLOC_CS);
    hevBufThreads = CreateEvent(NULL, FALSE, FALSE, NULL);      // auto-reset, not initially signalled
    if (hevBufThreads) {
        DEBUGALLOC(DEBUGALLOC_EVENT);
        return TRUE;
    }
    return FALSE;
}


void BufDeinit(void)
{
    if (hevBufThreads) {
        CloseHandle(hevBufThreads);
        DEBUGFREE(DEBUGALLOC_EVENT);
    }
    DEBUGFREE(DEBUGALLOC_CS);
    DeleteCriticalSection(&csBuffers);
}


/*  BufEnter - Gates threads using the buffer pool
 *
 *  Originally, this function was very simple.  If cBufThreads dropped
 *  below zero, it waited for the supportable thread count to rise again
 *  before letting another thread enter.
 *
 *  Unfortunately, because we retain dirty data indefinitely, in the hopes
 *  that it can eventually be committed, dirty buffers may not actually be
 *  usable if the data cannot actually be committed at this time (eg, card
 *  is bad, card has been removed, etc).  So, now we charge uncommitable
 *  buffers against cBufThreads as well.
 *
 *  ENTRY
 *      fForce - TRUE to force entry, FALSE if not
 *
 *  EXIT
 *      TRUE if successful, FALSE if not (SetLastError is already set)
 *
 *  NOTES
 *      Called at the start of *all* FATFS API entry points, either directly
 *      or via FATEnter.
 */

BOOL BufEnter(BOOL fForce)
{
    if (fForce) {
        // Keep the buffer thread count balanced, but don't tarry
        InterlockedDecrement(&cBufThreads);
        return TRUE;
    }

    if (cLoads == 0) {
        // Any non-forced request during unloading is promptly failed
        SetLastError(ERROR_NOT_READY);
        return FALSE;
    }

    if (InterlockedDecrement(&cBufThreads) < 0) {

        // We have exceeded the number of threads that the buffer pool
        // can handle simultaneously.  We shall wait on an event that will
        // be set as soon as someone increments cBufThreads from within
        // negative territory.

        WaitForSingleObject(hevBufThreads, INFINITE);
    }
    return TRUE;
}


/*  BufExit - Gates threads finished with the buffer pool
 *
 *  ENTRY
 *      None
 *
 *  EXIT
 *      None
 *
 *  NOTES
 *      Called at the end of *all* FATFS API entry points, either directly
 *      or via FATExit.
 */

void BufExit()
{
    if (InterlockedIncrement(&cBufThreads) <= 0) {
        SetEvent(hevBufThreads);
    }
}


/*  NewBuffer - allocate a new buffer
 *
 *  ENTRY
 *      cb - size of buffer, in bytes
 *      ppbCarve - pointer to address of buffer memory to carve up;
 *      if either the pointer or the address it points is NULL, then
 *      we will allocate memory for the buffer internally.
 *
 *  EXIT
 *      pointer to buffer, NULL if error.  Note that this allocates
 *      both a BUF structure and the block of memory referenced by the
 *      BUF structure that is actually used to cache the disk data.
 */

__inline PBUF NewBuffer(DWORD cb, PBYTE *ppbCarve)
{
    PBUF pbuf;

    pbuf = (PBUF)LocalAlloc(LPTR, sizeof(BUF));

    if (pbuf) {

        DEBUGALLOC(sizeof(BUF));

        if (ppbCarve && *ppbCarve) {
            pbuf->b_pdata = *ppbCarve;
            pbuf->b_flags |= BUF_CARVED;
            *ppbCarve += cb;
        }
        else {
            if (flBuf & GBUF_LOCALALLOC) {
                pbuf->b_pdata = (PVOID)LocalAlloc(LMEM_FIXED, cb);
            }
            else {
                pbuf->b_pdata = VirtualAlloc(0,
                                             cb,
                                             MEM_RESERVE|MEM_COMMIT,
                                           //MEM_RESERVE|MEM_MAPPED,
                                             PAGE_READWRITE
                                           //PAGE_NOACCESS
                                            );
            }
            if (!pbuf->b_pdata) {
                DEBUGFREE(sizeof(BUF));
                VERIFYNULL(LocalFree((HLOCAL)pbuf));
                return NULL;
            }
            DEBUGALLOC(cb);
        }
    }
    return pbuf;
}


/*  AllocBufferPool - pre-allocate all buffers in buffer pool
 *
 *  ENTRY
 *      pvol - pointer to VOLUME currently being mounted
 *
 *  EXIT
 *      TRUE if buffer pool successfully (or already) allocated.  Every
 *      successful call must ultimately be matched by a call to
 *      FreeBufferPool;  only when the last volume has called FreeBufferPool
 *      will the pool actually be deallocated.
 *
 *  NOTES
 *      This function can fail if (a) the minimum number of buffers
 *      could not be allocated, or (b) the buffer pool was already allocated
 *      but the size of the buffers cannot accomodate the sector size of
 *      this particular volume.
 */

BOOL AllocBufferPool(PVOLUME pvol)
{
    ASSERT(OWNCRITICALSECTION(&pvol->v_cs));

    if (cBufVolumes > 0) {

        
#ifdef BIG_BUFFERS
        if (cbBuf < pvol->v_pdsk->d_diActive.di_bytes_per_sect)
            return FALSE;
#else
        if (cbBuf != pvol->v_pdsk->d_diActive.di_bytes_per_sect)
            return FALSE;
#endif
    }

    // If the current volume is already using the buffer pool,
    // then we're done.  Otherwise, increment total buffer pool clients.

    EnterCriticalSection(&csBuffers);

    // If the volume is already buffered, then we can skip most of this
    // work, but we'll still need to perform the recycled check below, because
    // if the volume changed on us, we need to throw away all its buffers.

    if (!(pvol->v_flags & VOLF_BUFFERED)) {

        pvol->v_flags |= VOLF_BUFFERED;