allocsup.c File Reference

#include "fatprocs.h"

Include dependency graph for allocsup.c:

Go to the source code of this file.

Macros
#define	BugCheckFileId   (FAT_BUG_CHECK_ALLOCSUP)
#define	Dbg   (DEBUG_TRACE_ALLOCSUP)
#define	FatMin(a, b)   ((a) < (b) ? (a) : (b))
#define	FAT_PREFETCH_PAGE_COUNT   0x100
#define	ASSERT_CURRENT_WINDOW_GOOD(VCB)
#define	FatLockFreeClusterBitMap(VCB)
#define	FatUnlockFreeClusterBitMap(VCB)
#define	FatIsClusterFree(IRPCONTEXT, VCB, FAT_INDEX)    (RtlCheckBit(&(VCB)->FreeClusterBitMap,(FAT_INDEX)-2) == 0)
#define	FatFreeClusters(IRPCONTEXT, VCB, FAT_INDEX, CLUSTER_COUNT)
#define	FatAllocateClusters(IRPCONTEXT, VCB, FAT_INDEX, CLUSTER_COUNT)
#define	FatUnreserveClusters(IRPCONTEXT, VCB, FAT_INDEX, CLUSTER_COUNT)
#define	FatReserveClusters(IRPCONTEXT, VCB, FAT_INDEX, CLUSTER_COUNT)
#define	FatFindFreeClusterRun(IRPCONTEXT, VCB, CLUSTER_COUNT, CLUSTER_HINT)
#define	MAX_CLUSTER_BITMAP_SIZE   (1 << 16)
#define	FatWindowOfCluster(C)   (((C) - 2) / MAX_CLUSTER_BITMAP_SIZE)
#define	MAX_ZERO_MDL_SIZE   (1*1024*1024)
#define	MAXCOUNTCLUS   0x10000
#define	COUNTSAVEDBCBS   ((MAXCOUNTCLUS * sizeof(FAT_ENTRY) / PAGE_SIZE) + 2)

Functions
VOID	FatLookupFatEntry (IN PIRP_CONTEXT IrpContext, IN PVCB Vcb, IN ULONG FatIndex, IN OUT PULONG FatEntry, IN OUT PFAT_ENUMERATION_CONTEXT Context)
VOID	FatSetFatRun (IN PIRP_CONTEXT IrpContext, IN PVCB Vcb, IN ULONG StartingFatIndex, IN ULONG ClusterCount, IN BOOLEAN ChainTogether)
UCHAR	FatLogOf (IN ULONG Value)
INLINE ULONG	FatSelectBestWindow (IN PVCB Vcb)
VOID	FatSetupAllocationSupport (IN PIRP_CONTEXT IrpContext, IN PVCB Vcb)
VOID	FatTearDownAllocationSupport (IN PIRP_CONTEXT IrpContext, IN PVCB Vcb)
	_Requires_lock_held_ (_Global_critical_region_)
CLUSTER_TYPE	FatInterpretClusterType (IN PVCB Vcb, IN FAT_ENTRY Entry)
VOID	FatExamineFatEntries (IN PIRP_CONTEXT IrpContext, IN PVCB Vcb, IN ULONG StartIndex OPTIONAL, IN ULONG EndIndex OPTIONAL, IN BOOLEAN SetupWindows, IN PFAT_WINDOW SwitchToWindow OPTIONAL, IN PULONG BitMapBuffer OPTIONAL)

Macro Definition Documentation

ASSERT_CURRENT_WINDOW_GOOD

#define ASSERT_CURRENT_WINDOW_GOOD

(

VCB

)

Definition at line 83 of file allocsup.c.

BugCheckFileId

#define BugCheckFileId   (FAT_BUG_CHECK_ALLOCSUP)

Definition at line 22 of file allocsup.c.

COUNTSAVEDBCBS

#define COUNTSAVEDBCBS   ((MAXCOUNTCLUS * sizeof(FAT_ENTRY) / PAGE_SIZE) + 2)

Dbg

#define Dbg   (DEBUG_TRACE_ALLOCSUP)

Definition at line 28 of file allocsup.c.

FAT_PREFETCH_PAGE_COUNT

#define FAT_PREFETCH_PAGE_COUNT   0x100

Definition at line 36 of file allocsup.c.

FatAllocateClusters

#define FatAllocateClusters	(		IRPCONTEXT,
			VCB,
			FAT_INDEX,
			CLUSTER_COUNT
	)

Value:

    {      \
    if ((CLUSTER_COUNT) == 1) {                                            \
        FatSetFatEntry((IRPCONTEXT),(VCB),(FAT_INDEX),FAT_CLUSTER_LAST);   \
    } else {                                                               \
        FatSetFatRun((IRPCONTEXT),(VCB),(FAT_INDEX),(CLUSTER_COUNT),TRUE); \
    }                                                                      \
}

Definition at line 158 of file allocsup.c.

FatFindFreeClusterRun

#define FatFindFreeClusterRun	(		IRPCONTEXT,
			VCB,
			CLUSTER_COUNT,
			CLUSTER_HINT
	)

Value:

    ( \
    (CLUSTER_COUNT == 1) &&                                                \
    FatIsClusterFree((IRPCONTEXT), (VCB), (CLUSTER_HINT)) ?                \
        (CLUSTER_HINT) :                                                   \
        RtlFindClearBits( &(VCB)->FreeClusterBitMap,                       \
                          (CLUSTER_COUNT),                                 \
                          (CLUSTER_HINT) - 2) + 2                          \
)

Definition at line 229 of file allocsup.c.

FatFreeClusters

#define FatFreeClusters	(		IRPCONTEXT,
			VCB,
			FAT_INDEX,
			CLUSTER_COUNT
	)

Value:

    {             \
    if ((CLUSTER_COUNT) == 1) {                                               \
        FatSetFatEntry((IRPCONTEXT),(VCB),(FAT_INDEX),FAT_CLUSTER_AVAILABLE); \
    } else {                                                                  \
        FatSetFatRun((IRPCONTEXT),(VCB),(FAT_INDEX),(CLUSTER_COUNT),FALSE);   \
    }                                                                         \
}

Definition at line 140 of file allocsup.c.

FatIsClusterFree

#define FatIsClusterFree	(		IRPCONTEXT,
			VCB,
			FAT_INDEX
	)		(RtlCheckBit(&(VCB)->FreeClusterBitMap,(FAT_INDEX)-2) == 0)

Definition at line 127 of file allocsup.c.

FatLockFreeClusterBitMap

#define FatLockFreeClusterBitMap

(

VCB

)

Value:

    {                         \
    NT_ASSERT(KeAreApcsDisabled());                             \
    ExAcquireFastMutexUnsafe( &(VCB)->FreeClusterBitMapMutex ); \
    ASSERT_CURRENT_WINDOW_GOOD(VCB)                             \
}

Definition at line 99 of file allocsup.c.

FatMin

#define FatMin	(		a,
			b
	)		((a) < (b) ? (a) : (b))

Definition at line 30 of file allocsup.c.

FatReserveClusters

#define FatReserveClusters	(		IRPCONTEXT,
			VCB,
			FAT_INDEX,
			CLUSTER_COUNT
	)

Value:

    {                        \
    ULONG _AfterRun = (FAT_INDEX) + (CLUSTER_COUNT);                                        \
    NT_ASSERT( (FAT_INDEX) + (CLUSTER_COUNT) - 2 <= (VCB)->FreeClusterBitMap.SizeOfBitMap );\
    NT_ASSERT( (FAT_INDEX) >= 2);                                                           \
    RtlSetBits(&(VCB)->FreeClusterBitMap,(FAT_INDEX)-2,(CLUSTER_COUNT));                    \
                                                                                            \
    if (_AfterRun - 2 >= (VCB)->FreeClusterBitMap.SizeOfBitMap) {                           \
        _AfterRun = 2;                                                                      \
    }                                                                                       \
    if (RtlCheckBit(&(VCB)->FreeClusterBitMap, _AfterRun - 2))  {                                   \
        (VCB)->ClusterHint = RtlFindClearBits( &(VCB)->FreeClusterBitMap, 1, _AfterRun - 2) + 2;    \
        if (1 == (VCB)->ClusterHint)  {                                                             \
            (VCB)->ClusterHint = 2;                                                         \
        }                                                                                   \
    }                                                                                       \
    else {                                                                                  \
        (VCB)->ClusterHint = _AfterRun;                                                     \
    }                                                                                       \
}

Definition at line 197 of file allocsup.c.

FatUnlockFreeClusterBitMap

#define FatUnlockFreeClusterBitMap

(

VCB

)

Value:

    {                       \
    ASSERT_CURRENT_WINDOW_GOOD(VCB)                             \
    NT_ASSERT(KeAreApcsDisabled());                             \
    ExReleaseFastMutexUnsafe( &(VCB)->FreeClusterBitMapMutex ); \
}

Definition at line 112 of file allocsup.c.

FatUnreserveClusters

#define FatUnreserveClusters	(		IRPCONTEXT,
			VCB,
			FAT_INDEX,
			CLUSTER_COUNT
	)

Value:

    {                      \
    NT_ASSERT( (FAT_INDEX) + (CLUSTER_COUNT) - 2 <= (VCB)->FreeClusterBitMap.SizeOfBitMap );\
    NT_ASSERT( (FAT_INDEX) >= 2);                                                           \
    RtlClearBits(&(VCB)->FreeClusterBitMap,(FAT_INDEX)-2,(CLUSTER_COUNT));                  \
    if ((FAT_INDEX) < (VCB)->ClusterHint) {                                                 \
        (VCB)->ClusterHint = (FAT_INDEX);                                                   \
    }                                                                                       \
}

Definition at line 176 of file allocsup.c.

FatWindowOfCluster

#define FatWindowOfCluster

(

C

)

(((C) - 2) / MAX_CLUSTER_BITMAP_SIZE)

Definition at line 253 of file allocsup.c.

MAX_CLUSTER_BITMAP_SIZE

#define MAX_CLUSTER_BITMAP_SIZE   (1 << 16)

Definition at line 247 of file allocsup.c.

MAX_ZERO_MDL_SIZE

#define MAX_ZERO_MDL_SIZE   (1*1024*1024)

Definition at line 2602 of file allocsup.c.

MAXCOUNTCLUS

#define MAXCOUNTCLUS   0x10000

Function Documentation

_Requires_lock_held_()

_Requires_lock_held_

(

_Global_critical_region_

)

Definition at line 617 of file allocsup.c.

{
    VBO CurrentVbo;
    LBO CurrentLbo;
    LBO PriorLbo;
 
    VBO FirstVboOfCurrentRun = 0;
    LBO FirstLboOfCurrentRun;
 
    BOOLEAN LastCluster;
    ULONG Runs;
 
    PVCB Vcb;
    FAT_ENTRY FatEntry;
    ULONG BytesPerCluster;
    ULARGE_INTEGER BytesOnVolume;
 
    FAT_ENUMERATION_CONTEXT Context;
 
    PAGED_CODE();
 
    Vcb = FcbOrDcb->Vcb;
 
 
    DebugTrace(+1, Dbg, "FatLookupFileAllocation\n", 0);
    DebugTrace( 0, Dbg, "  FcbOrDcb  = %p\n", FcbOrDcb);
    DebugTrace( 0, Dbg, "  Vbo       = %8lx\n", Vbo);
    DebugTrace( 0, Dbg, "  pLbo       = %8lx\n", Lbo);
    DebugTrace( 0, Dbg, "  pByteCount = %8lx\n", ByteCount);
    DebugTrace( 0, Dbg, "  pAllocated = %8lx\n", Allocated);
 
    Context.Bcb = NULL;
 
    *EndOnMax = FALSE;
 
    //
    //  Check the trivial case that the mapping is already in our
    //  Mcb.
    //
 
    if ( FatLookupMcbEntry(Vcb, &FcbOrDcb->Mcb, Vbo, Lbo, ByteCount, Index) ) {
 
        *Allocated = TRUE;
 
        NT_ASSERT( *ByteCount != 0 );
 
        //
        //  Detect the overflow case, trim and claim the condition.
        //
 
        if (Vbo + *ByteCount == 0) {
 
            *EndOnMax = TRUE;
        }
 
        DebugTrace( 0, Dbg, "Found run in Mcb.\n", 0);
        DebugTrace(-1, Dbg, "FatLookupFileAllocation -> (VOID)\n", 0);
        return;
    }
 
    //
    //  Initialize the Vcb, the cluster size, LastCluster, and
    //  FirstLboOfCurrentRun (to be used as an indication of the first
    //  iteration through the following while loop).
    //
 
    BytesPerCluster = 1 << Vcb->AllocationSupport.LogOfBytesPerCluster;
 
    BytesOnVolume.QuadPart = UInt32x32To64( Vcb->AllocationSupport.NumberOfClusters, BytesPerCluster );
 
    LastCluster = FALSE;
    FirstLboOfCurrentRun = 0;
 
    //
    //  Discard the case that the request extends beyond the end of
    //  allocation.  Note that if the allocation size if not known
    //  AllocationSize is set to 0xffffffff.
    //
 
    if ( Vbo >= FcbOrDcb->Header.AllocationSize.LowPart ) {
 
        *Allocated = FALSE;
 
        DebugTrace( 0, Dbg, "Vbo beyond end of file.\n", 0);
        DebugTrace(-1, Dbg, "FatLookupFileAllocation -> (VOID)\n", 0);
        return;
    }
 
    //
    //  The Vbo is beyond the last Mcb entry.  So we adjust Current Vbo/Lbo
    //  and FatEntry to describe the beginning of the last entry in the Mcb.
    //  This is used as initialization for the following loop.
    //
    //  If the Mcb was empty, we start at the beginning of the file with
    //  CurrentVbo set to 0 to indicate a new run.
    //
 
    if (FatLookupLastMcbEntry( Vcb, &FcbOrDcb->Mcb, &CurrentVbo, &CurrentLbo, &Runs )) {
 
        DebugTrace( 0, Dbg, "Current Mcb size = %8lx.\n", CurrentVbo + 1);
 
        CurrentVbo -= (BytesPerCluster - 1);
        CurrentLbo -= (BytesPerCluster - 1);
 
        //
        //  Convert an index to a count.
        //
 
        Runs += 1;
 
    } else {
 
        DebugTrace( 0, Dbg, "Mcb empty.\n", 0);
 
        //
        //  Check for an FcbOrDcb that has no allocation
        //
 
        if (FcbOrDcb->FirstClusterOfFile == 0) {
 
            *Allocated = FALSE;
 
            DebugTrace( 0, Dbg, "File has no allocation.\n", 0);
            DebugTrace(-1, Dbg, "FatLookupFileAllocation -> (VOID)\n", 0);
            return;
 
        } else {
 
            CurrentVbo = 0;
            CurrentLbo = FatGetLboFromIndex( Vcb, FcbOrDcb->FirstClusterOfFile );
            FirstVboOfCurrentRun = CurrentVbo;
            FirstLboOfCurrentRun = CurrentLbo;
 
            Runs = 0;
 
            DebugTrace( 0, Dbg, "First Lbo of file = %8lx\n", CurrentLbo);
        }
    }
 
    //
    //  Now we know that we are looking up a valid Vbo, but it is
    //  not in the Mcb, which is a monotonically increasing list of
    //  Vbo's.  Thus we have to go to the Fat, and update
    //  the Mcb as we go.  We use a try-finally to unpin the page
    //  of fat hanging around.  Also we mark *Allocated = FALSE, so that
    //  the caller wont try to use the data if we hit an exception.
    //
 
    *Allocated = FALSE;
 
    _SEH2_TRY {
 
        FatEntry = (FAT_ENTRY)FatGetIndexFromLbo( Vcb, CurrentLbo );
 
        //
        //  ASSERT that CurrentVbo and CurrentLbo are now cluster alligned.
        //  The assumption here, is that only whole clusters of Vbos and Lbos
        //  are mapped in the Mcb.
        //
 
        NT_ASSERT( ((CurrentLbo - Vcb->AllocationSupport.FileAreaLbo)
                                                    % BytesPerCluster == 0) &&
                (CurrentVbo % BytesPerCluster == 0) );
 
        //
        //  Starting from the first Vbo after the last Mcb entry, scan through
        //  the Fat looking for our Vbo. We continue through the Fat until we
        //  hit a noncontiguity beyond the desired Vbo, or the last cluster.
        //
 
        while ( !LastCluster ) {
 
            //
            //  Get the next fat entry, and update our Current variables.
            //
 
            FatLookupFatEntry( IrpContext, Vcb, FatEntry, (PULONG)&FatEntry, &Context );
 
            PriorLbo = CurrentLbo;
            CurrentLbo = FatGetLboFromIndex( Vcb, FatEntry );
            CurrentVbo += BytesPerCluster;
 
            switch ( FatInterpretClusterType( Vcb, FatEntry )) {
 
            //
            //  Check for a break in the Fat allocation chain.
            //
 
            case FatClusterAvailable:
            case FatClusterReserved:
            case FatClusterBad:
 
                DebugTrace( 0, Dbg, "Break in allocation chain, entry = %d\n", FatEntry);
                DebugTrace(-1, Dbg, "FatLookupFileAllocation -> Fat Corrupt.  Raise Status.\n", 0);
 
                FatPopUpFileCorrupt( IrpContext, FcbOrDcb );
                FatRaiseStatus( IrpContext, STATUS_FILE_CORRUPT_ERROR );
                break;
 
            //
            //  If this is the last cluster, we must update the Mcb and
            //  exit the loop.
            //
 
            case FatClusterLast:
 
                //
                //  Assert we know where the current run started.  If the
                //  Mcb was empty when we were called, thenFirstLboOfCurrentRun
                //  was set to the start of the file.  If the Mcb contained an
                //  entry, then FirstLboOfCurrentRun was set on the first
                //  iteration through the loop.  Thus if FirstLboOfCurrentRun
                //  is 0, then there was an Mcb entry and we are on our first
                //  iteration, meaing that the last cluster in the Mcb was
                //  really the last allocated cluster, but we checked Vbo
                //  against AllocationSize, and found it OK, thus AllocationSize
                //  must be too large.
                //
                //  Note that, when we finally arrive here, CurrentVbo is actually
                //  the first Vbo beyond the file allocation and CurrentLbo is
                //  meaningless.
                //
 
                DebugTrace( 0, Dbg, "Read last cluster of file.\n", 0);
 
                //
                //  Detect the case of the maximal file.  Note that this really isn't
                //  a proper Vbo - those are zero-based, and this is a one-based number.
                //  The maximal file, of 2^32 - 1 bytes, has a maximum byte offset of
                //  2^32 - 2.
                //
                //  Just so we don't get confused here.
                //
 
                if (CurrentVbo == 0) {
 
                    *EndOnMax = TRUE;
                    CurrentVbo -= 1;
                }
 
                LastCluster = TRUE;
 
                if (FirstLboOfCurrentRun != 0 ) {
 
                    DebugTrace( 0, Dbg, "Adding a run to the Mcb.\n", 0);
                    DebugTrace( 0, Dbg, "  Vbo    = %08lx.\n", FirstVboOfCurrentRun);
                    DebugTrace( 0, Dbg, "  Lbo    = %08lx.\n", FirstLboOfCurrentRun);
                    DebugTrace( 0, Dbg, "  Length = %08lx.\n", CurrentVbo - FirstVboOfCurrentRun);
 
                    (VOID)FatAddMcbEntry( Vcb,
                                          &FcbOrDcb->Mcb,
                                          FirstVboOfCurrentRun,
                                          FirstLboOfCurrentRun,
                                          CurrentVbo - FirstVboOfCurrentRun );
 
                    Runs += 1;
                }
 
                //
                //  Being at the end of allocation, make sure we have found
                //  the Vbo.  If we haven't, seeing as we checked VBO
                //  against AllocationSize, the real disk allocation is less
                //  than that of AllocationSize.  This comes about when the
                //  real allocation is not yet known, and AllocaitonSize
                //  contains MAXULONG.
                //
                //  KLUDGE! - If we were called by FatLookupFileAllocationSize
                //  Vbo is set to MAXULONG - 1, and AllocationSize to the lookup
                //  hint. Thus we merrily go along looking for a match that isn't
                //  there, but in the meantime building an Mcb.  If this is
                //  the case, fill in AllocationSize and return.
                //
 
                if ( Vbo == MAXULONG - 1 ) {
 
                    *Allocated = FALSE;
 
                    FcbOrDcb->Header.AllocationSize.QuadPart = CurrentVbo;
 
                    DebugTrace( 0, Dbg, "New file allocation size = %08lx.\n", CurrentVbo);
                    try_return ( NOTHING );
                }
 
                //
                //  We will lie ever so slightly if we really terminated on the
                //  maximal byte of a file.  It is really allocated.
                //
 
                if (Vbo >= CurrentVbo && !*EndOnMax) {
 
                    *Allocated = FALSE;
                    try_return ( NOTHING );
                }
 
                break;
 
            //
            //  This is a continuation in the chain.  If the run has a
            //  discontiguity at this point, update the Mcb, and if we are beyond
            //  the desired Vbo, this is the end of the run, so set LastCluster
            //  and exit the loop.
            //
 
            case FatClusterNext:
 
                //
                //  This is the loop check.  The Vbo must not be bigger than the size of
                //  the volume, and the Vbo must not have a) wrapped and b) not been at the
                //  very last cluster in the chain, for the case of the maximal file.
                //
 
                if ( CurrentVbo == 0 ||
                     (BytesOnVolume.HighPart == 0 && CurrentVbo > BytesOnVolume.LowPart)) {
 
                    FatPopUpFileCorrupt( IrpContext, FcbOrDcb );
                    FatRaiseStatus( IrpContext, STATUS_FILE_CORRUPT_ERROR );
                }
 
                if ( PriorLbo + BytesPerCluster != CurrentLbo ) {
 
                    //
                    //  Note that on the first time through the loop
                    //  (FirstLboOfCurrentRun == 0), we don't add the
                    //  run to the Mcb since it curresponds to the last
                    //  run already stored in the Mcb.
                    //
 
                    if ( FirstLboOfCurrentRun != 0 ) {
 
                        DebugTrace( 0, Dbg, "Adding a run to the Mcb.\n", 0);
                        DebugTrace( 0, Dbg, "  Vbo    = %08lx.\n", FirstVboOfCurrentRun);
                        DebugTrace( 0, Dbg, "  Lbo    = %08lx.\n", FirstLboOfCurrentRun);
                        DebugTrace( 0, Dbg, "  Length = %08lx.\n", CurrentVbo - FirstVboOfCurrentRun);
 
                        FatAddMcbEntry( Vcb,
                                        &FcbOrDcb->Mcb,
                                        FirstVboOfCurrentRun,
                                        FirstLboOfCurrentRun,
                                        CurrentVbo - FirstVboOfCurrentRun );
 
                        Runs += 1;
                    }
 
                    //
                    //  Since we are at a run boundry, with CurrentLbo and
                    //  CurrentVbo being the first cluster of the next run,
                    //  we see if the run we just added encompases the desired
                    //  Vbo, and if so exit.  Otherwise we set up two new
                    //  First*boOfCurrentRun, and continue.
                    //
 
                    if (CurrentVbo > Vbo) {
 
                        LastCluster = TRUE;
 
                    } else {
 
                        FirstVboOfCurrentRun = CurrentVbo;
                        FirstLboOfCurrentRun = CurrentLbo;
                    }
                }
                break;
 
            default:
 
                DebugTrace(0, Dbg, "Illegal Cluster Type.\n", FatEntry);
 
#ifdef _MSC_VER
#pragma prefast( suppress: 28159, "we bugcheck here because our internal data structures are seriously corrupted if this happens" )
#endif
                FatBugCheck( 0, 0, 0 );
 
                break;
 
            } // switch()
        } // while()
 
        //
        //  Load up the return parameters.
        //
        //  On exit from the loop, Vbo still contains the desired Vbo, and
        //  CurrentVbo is the first byte after the run that contained the
        //  desired Vbo.
        //
 
        *Allocated = TRUE;
 
        *Lbo = FirstLboOfCurrentRun + (Vbo - FirstVboOfCurrentRun);
 
        *ByteCount = CurrentVbo - Vbo;
 
        if (ARGUMENT_PRESENT(Index)) {
 
            //
            //  Note that Runs only needs to be accurate with respect to where we
            //  ended.  Since partial-lookup cases will occur without exclusive
            //  synchronization, the Mcb itself may be much bigger by now.
            //
 
            *Index = Runs - 1;
        }
 
    try_exit: NOTHING;
 
    } _SEH2_FINALLY {
 
        DebugUnwind( FatLookupFileAllocation );
 
        //
        //  We are done reading the Fat, so unpin the last page of fat
        //  that is hanging around
        //
 
        FatUnpinBcb( IrpContext, Context.Bcb );
 
        DebugTrace(-1, Dbg, "FatLookupFileAllocation -> (VOID)\n", 0);
    } _SEH2_END;
 
    return;
}

FatExamineFatEntries()

VOID FatExamineFatEntries	(	IN PIRP_CONTEXT	IrpContext,
		IN PVCB	Vcb,
		IN ULONG StartIndex	OPTIONAL,
		IN ULONG EndIndex	OPTIONAL,
		IN BOOLEAN	SetupWindows,
		IN PFAT_WINDOW SwitchToWindow	OPTIONAL,
		IN PULONG BitMapBuffer	OPTIONAL
	)

Definition at line 4720 of file allocsup.c.

{
    ULONG FatIndexBitSize;
    ULONG Page = 0;
    ULONG Offset = 0;
    ULONG FatIndex;
    FAT_ENTRY FatEntry = FAT_CLUSTER_AVAILABLE;
    FAT_ENTRY FirstFatEntry = FAT_CLUSTER_AVAILABLE;
    PUSHORT FatBuffer;
    PVOID pv;
    PBCB Bcb = NULL;
    ULONG EntriesPerWindow;
 
    ULONG ClustersThisRun;
    ULONG StartIndexOfThisRun;
 
    PULONG FreeClusterCount = NULL;
 
    PFAT_WINDOW CurrentWindow = NULL;
 
    PVOID NewBitMapBuffer = NULL;
    PRTL_BITMAP BitMap = NULL;
    RTL_BITMAP PrivateBitMap;
 
    ULONG ClusterSize = 0;
    ULONG PrefetchPages = 0;
    ULONG FatPages = 0;
 
    VBO BadClusterVbo = 0;
    LBO Lbo = 0;
 
    enum RunType {
        FreeClusters,
        AllocatedClusters,
        UnknownClusters
    } CurrentRun;
 
    PAGED_CODE();
 
    //
    //  Now assert correct usage.
    //
 
    FatIndexBitSize = Vcb->AllocationSupport.FatIndexBitSize;
 
    NT_ASSERT( !(SetupWindows && (SwitchToWindow || BitMapBuffer)));
    NT_ASSERT( !(SetupWindows && FatIndexBitSize != 32));
 
    if (Vcb->NumberOfWindows > 1) {
 
        //
        //  FAT32: Calculate the number of FAT entries covered by a window.  This is
        //  equal to the number of bits in the freespace bitmap,  the size of which
        //  is hardcoded.
        //
 
        EntriesPerWindow = MAX_CLUSTER_BITMAP_SIZE;
 
    } else {
 
        EntriesPerWindow = Vcb->AllocationSupport.NumberOfClusters;
    }
 
    //
    //  We will also fill in the cumulative count of free clusters for
    //  the entire volume.  If this is not appropriate, NULL it out
    //  shortly.
    //
 
    FreeClusterCount = &Vcb->AllocationSupport.NumberOfFreeClusters;
 
    if (SetupWindows) {
 
        NT_ASSERT(BitMapBuffer == NULL);
 
        //
        //  In this case we're just supposed to scan the fat and set up
        //  the information regarding where the buckets fall and how many
        //  free clusters are in each.
        //
        //  It is fine to monkey with the real windows, we must be able
        //  to do this to activate the volume.
        //
 
        BitMap = NULL;
 
        CurrentWindow = &Vcb->Windows[0];
        CurrentWindow->FirstCluster = StartIndex;
        CurrentWindow->ClustersFree = 0;
 
        //
        //  We always wish to calculate total free clusters when
        //  setting up the FAT windows.
        //
 
    } else if (BitMapBuffer == NULL) {
 
        //
        //  We will be filling in the free cluster bitmap for the volume.
        //  Careful, we can raise out of here and be hopelessly hosed if
        //  we built this up in the main bitmap/window itself.
        //
        //  For simplicity's sake, we'll do the swap for everyone. FAT32
        //  provokes the need since we can't tolerate partial results
        //  when switching windows.
        //
 
        NT_ASSERT( SwitchToWindow );
 
        CurrentWindow = SwitchToWindow;
        StartIndex = CurrentWindow->FirstCluster;
        EndIndex = CurrentWindow->LastCluster;
 
        BitMap = &PrivateBitMap;
        NewBitMapBuffer = FsRtlAllocatePoolWithTag( PagedPool,
                                                    (EntriesPerWindow + 7) / 8,
                                                    TAG_FAT_BITMAP );
 
        RtlInitializeBitMap( &PrivateBitMap,
                             NewBitMapBuffer,
                             EndIndex - StartIndex + 1);
 
        if ((FatIndexBitSize == 32) &&
            (Vcb->NumberOfWindows > 1)) {
 
            //
            //  We do not wish count total clusters here.
            //
 
            FreeClusterCount = NULL;
 
        }
 
    } else {
 
        BitMap = &PrivateBitMap;
        RtlInitializeBitMap(&PrivateBitMap,
                            BitMapBuffer,
                            EndIndex - StartIndex + 1);
 
        //
        //  We do not count total clusters here.
        //
 
        FreeClusterCount = NULL;
    }
 
    //
    //  Now, our start index better be in the file heap.
    //
 
    NT_ASSERT( StartIndex >= 2 );
 
    _SEH2_TRY {
 
        //
        //  Pick up the initial chunk of the FAT and first entry.
        //
 
        if (FatIndexBitSize == 12) {
 
            //
            //  We read in the entire fat in the 12 bit case.
            //
 
            FatReadVolumeFile( IrpContext,
                               Vcb,
                               FatReservedBytes( &Vcb->Bpb ),
                               FatBytesPerFat( &Vcb->Bpb ),
                               &Bcb,
                               (PVOID *)&FatBuffer );
 
            FatLookup12BitEntry(FatBuffer, 0, &FirstFatEntry);
 
        } else {
 
            //
            //  Read in one page of fat at a time.  We cannot read in the
            //  all of the fat we need because of cache manager limitations.
            //
 
            ULONG BytesPerEntry = FatIndexBitSize >> 3;
 
            FatPages = (FatReservedBytes(&Vcb->Bpb) + FatBytesPerFat(&Vcb->Bpb) + (PAGE_SIZE - 1)) / PAGE_SIZE;
            Page = (FatReservedBytes(&Vcb->Bpb) + StartIndex * BytesPerEntry) / PAGE_SIZE;
 
            Offset = Page * PAGE_SIZE;
 
            //
            //  Prefetch the FAT entries in memory for optimal performance.
            //
 
            PrefetchPages = FatPages - Page;
 
            if (PrefetchPages > FAT_PREFETCH_PAGE_COUNT) {
 
                PrefetchPages = ALIGN_UP_BY(Page, FAT_PREFETCH_PAGE_COUNT) - Page;
            }
 
#if (NTDDI_VERSION >= NTDDI_WIN8)
            FatPrefetchPages( IrpContext,
                              Vcb->VirtualVolumeFile,
                              Page,
                              PrefetchPages );
#endif
 
            FatReadVolumeFile( IrpContext,
                               Vcb,
                               Offset,
                               PAGE_SIZE,
                               &Bcb,
                               &pv);
 
            if (FatIndexBitSize == 32) {
 
                FatBuffer = (PUSHORT)((PUCHAR)pv +
                            (FatReservedBytes(&Vcb->Bpb) + StartIndex * BytesPerEntry) %
                                 PAGE_SIZE);
 
                FirstFatEntry = *((PULONG)FatBuffer);
                FirstFatEntry = FirstFatEntry & FAT32_ENTRY_MASK;
 
            } else {
 
                FatBuffer = (PUSHORT)((PUCHAR)pv +
                            FatReservedBytes(&Vcb->Bpb) % PAGE_SIZE) + 2;
 
                FirstFatEntry = *FatBuffer;
            }
 
        }
 
        ClusterSize = 1 << (Vcb->AllocationSupport.LogOfBytesPerCluster);
 
        CurrentRun = (FirstFatEntry == FAT_CLUSTER_AVAILABLE) ?
                     FreeClusters : AllocatedClusters;
 
        StartIndexOfThisRun = StartIndex;
 
        for (FatIndex = StartIndex; FatIndex <= EndIndex; FatIndex++) {
 
            if (FatIndexBitSize == 12) {
 
                FatLookup12BitEntry(FatBuffer, FatIndex, &FatEntry);
 
            } else {
 
                //
                //  If we are setting up the FAT32 windows and have stepped into a new
                //  bucket, finalize this one and move forward.
                //
 
                if (SetupWindows &&
                    FatIndex > StartIndex &&
                    (FatIndex - 2) % EntriesPerWindow == 0) {
 
                    CurrentWindow->LastCluster = FatIndex - 1;
 
                    if (CurrentRun == FreeClusters) {
 
                        //
                        //  We must be counting clusters in order to modify the
                        //  contents of the window.
                        //
 
                        NT_ASSERT( FreeClusterCount );
 
                        ClustersThisRun = FatIndex - StartIndexOfThisRun;
                        CurrentWindow->ClustersFree += ClustersThisRun;
 
                        if (FreeClusterCount) {
                            *FreeClusterCount += ClustersThisRun;
                        }
 
                    } else {
 
                        NT_ASSERT(CurrentRun == AllocatedClusters);
 
                    }
 
                    StartIndexOfThisRun = FatIndex;
                    CurrentRun = UnknownClusters;
 
                    CurrentWindow++;
                    CurrentWindow->ClustersFree = 0;
                    CurrentWindow->FirstCluster = FatIndex;
                }
 
                //
                //  If we just stepped onto a new page, grab a new pointer.
                //
 
                if (((ULONG_PTR)FatBuffer & (PAGE_SIZE - 1)) == 0) {
 
                    FatUnpinBcb( IrpContext, Bcb );
 
                    Page++;
                    Offset += PAGE_SIZE;
 
#if (NTDDI_VERSION >= NTDDI_WIN8)
                    //
                    //  If we have exhausted all the prefetch pages, prefetch the next chunk.
                    //
 
                    if (--PrefetchPages == 0) {
 
                        PrefetchPages = FatPages - Page;
 
                        if (PrefetchPages > FAT_PREFETCH_PAGE_COUNT) {
 
                            PrefetchPages = FAT_PREFETCH_PAGE_COUNT;
                        }
 
                        FatPrefetchPages( IrpContext,
                                          Vcb->VirtualVolumeFile,
                                          Page,
                                          PrefetchPages );
                    }
#endif
 
                    FatReadVolumeFile( IrpContext,
                                       Vcb,
                                       Offset,
                                       PAGE_SIZE,
                                       &Bcb,
                                       &pv );
 
                    FatBuffer = (PUSHORT)pv;
                }
 
                if (FatIndexBitSize == 32) {
 
#ifndef __REACTOS__
#ifdef _MSC_VER
#pragma warning( suppress: 4213 )
#endif
                    FatEntry = *((PULONG)FatBuffer)++;
                    FatEntry = FatEntry & FAT32_ENTRY_MASK;
#else
                    FatEntry = *((PULONG)FatBuffer);
                    FatBuffer += 2; /* PUSHORT FatBuffer */
                    FatEntry = FatEntry & FAT32_ENTRY_MASK;
#endif
 
                } else {
 
                    FatEntry = *FatBuffer;
                    FatBuffer += 1;
                }
            }
 
            if (CurrentRun == UnknownClusters) {
 
                CurrentRun = (FatEntry == FAT_CLUSTER_AVAILABLE) ?
                              FreeClusters : AllocatedClusters;
            }
 
            //
            //  Are we switching from a free run to an allocated run?
            //
 
            if (CurrentRun == FreeClusters &&
                FatEntry != FAT_CLUSTER_AVAILABLE) {
 
                ClustersThisRun = FatIndex - StartIndexOfThisRun;
 
                if (FreeClusterCount) {
 
                    *FreeClusterCount += ClustersThisRun;
                    CurrentWindow->ClustersFree += ClustersThisRun;
                }
 
                if (BitMap) {
 
                    RtlClearBits( BitMap,
                                  StartIndexOfThisRun - StartIndex,
                                  ClustersThisRun );
                }
 
                CurrentRun = AllocatedClusters;
                StartIndexOfThisRun = FatIndex;
            }
 
            //
            //  Are we switching from an allocated run to a free run?
            //
 
            if (CurrentRun == AllocatedClusters &&
                FatEntry == FAT_CLUSTER_AVAILABLE) {
 
                ClustersThisRun = FatIndex - StartIndexOfThisRun;
 
                if (BitMap) {
 
                    RtlSetBits( BitMap,
                                StartIndexOfThisRun - StartIndex,
                                ClustersThisRun );
                }
 
                CurrentRun = FreeClusters;
                StartIndexOfThisRun = FatIndex;
            }
 
            //
            //  If the entry is marked bad, add it to the bad block MCB
            //
 
            if ((SetupWindows || (Vcb->NumberOfWindows == 1)) &&
                (FatInterpretClusterType( Vcb, FatEntry ) == FatClusterBad)) {
 
                //
                //  This cluster is marked bad.
                //  Add it to the BadBlockMcb.
                //
 
                Lbo = FatGetLboFromIndex( Vcb, FatIndex );
                FatAddMcbEntry( Vcb, &Vcb->BadBlockMcb, BadClusterVbo, Lbo, ClusterSize );
                BadClusterVbo += ClusterSize;
            }
        }
 
        //
        //  If we finished the scan, then we know about all the possible bad clusters.
        //
 
        SetFlag( Vcb->VcbState, VCB_STATE_FLAG_BAD_BLOCKS_POPULATED);
 
        //
        //  Now we have to record the final run we encountered
        //
 
        ClustersThisRun = FatIndex - StartIndexOfThisRun;
 
        if (CurrentRun == FreeClusters) {
 
            if (FreeClusterCount) {
 
                *FreeClusterCount += ClustersThisRun;
                CurrentWindow->ClustersFree += ClustersThisRun;
            }
 
            if (BitMap) {
 
                RtlClearBits( BitMap,
                              StartIndexOfThisRun - StartIndex,
                              ClustersThisRun );
            }
 
        } else {
 
            if (BitMap) {
 
                RtlSetBits( BitMap,
                            StartIndexOfThisRun - StartIndex,
                            ClustersThisRun );
            }
        }
 
        //
        //  And finish the last window if we are in setup.
        //
 
        if (SetupWindows) {
 
            CurrentWindow->LastCluster = FatIndex - 1;
        }
 
        //
        //  Now switch the active window if required.  We've succesfully gotten everything
        //  nailed down.
        //
        //  If we were tracking the free cluster count, this means we should update the
        //  window.  This is the case of FAT12/16 initialization.
        //
 
        if (SwitchToWindow) {
 
            if (Vcb->FreeClusterBitMap.Buffer) {
 
                ExFreePool( Vcb->FreeClusterBitMap.Buffer );
            }
 
            RtlInitializeBitMap( &Vcb->FreeClusterBitMap,
                                 NewBitMapBuffer,
                                 EndIndex - StartIndex + 1 );
 
            NewBitMapBuffer = NULL;
 
            Vcb->CurrentWindow = SwitchToWindow;
            Vcb->ClusterHint = (ULONG)-1;
 
            if (FreeClusterCount) {
 
                NT_ASSERT( !SetupWindows );
 
                Vcb->CurrentWindow->ClustersFree = *FreeClusterCount;
            }
        }
 
        //
        //  Make sure plausible things occured ...
        //
 
        if (!SetupWindows && BitMapBuffer == NULL) {
 
            ASSERT_CURRENT_WINDOW_GOOD( Vcb );
        }
 
        NT_ASSERT(Vcb->AllocationSupport.NumberOfFreeClusters <= Vcb->AllocationSupport.NumberOfClusters);
 
    } _SEH2_FINALLY {
 
        //
        //  Unpin the last bcb and drop the temporary bitmap buffer if it exists.
        //
 
        FatUnpinBcb( IrpContext, Bcb);
 
        if (NewBitMapBuffer) {
 
            ExFreePool( NewBitMapBuffer );
        }
    } _SEH2_END;
}

Referenced by FatSetupAllocationSupport().

FatInterpretClusterType()

CLUSTER_TYPE FatInterpretClusterType	(	IN PVCB	Vcb,
		IN FAT_ENTRY	Entry
	)

Definition at line 3473 of file allocsup.c.

{
    DebugTrace(+1, Dbg, "InterpretClusterType\n", 0);
    DebugTrace( 0, Dbg, "  Vcb   = %p\n", Vcb);
    DebugTrace( 0, Dbg, "  Entry = %8lx\n", Entry);
 
    PAGED_CODE();
 
    switch(Vcb->AllocationSupport.FatIndexBitSize ) {
    case 32:
        Entry &= FAT32_ENTRY_MASK;
        break;
 
    case 12:
        NT_ASSERT( Entry <= 0xfff );
        if (Entry >= 0x0ff0) {
            Entry |= 0x0FFFF000;
        }
        break;
 
    default:
    case 16:
        NT_ASSERT( Entry <= 0xffff );
        if (Entry >= 0x0fff0) {
            Entry |= 0x0FFF0000;
        }
        break;
    }
 
    if (Entry == FAT_CLUSTER_AVAILABLE) {
 
        DebugTrace(-1, Dbg, "FatInterpretClusterType -> FatClusterAvailable\n", 0);
 
        return FatClusterAvailable;
 
    } else if (Entry < FAT_CLUSTER_RESERVED) {
 
        DebugTrace(-1, Dbg, "FatInterpretClusterType -> FatClusterNext\n", 0);
 
        return FatClusterNext;
 
    } else if (Entry < FAT_CLUSTER_BAD) {
 
        DebugTrace(-1, Dbg, "FatInterpretClusterType -> FatClusterReserved\n", 0);
 
        return FatClusterReserved;
 
    } else if (Entry == FAT_CLUSTER_BAD) {
 
        DebugTrace(-1, Dbg, "FatInterpretClusterType -> FatClusterBad\n", 0);
 
        return FatClusterBad;
 
    } else {
 
        DebugTrace(-1, Dbg, "FatInterpretClusterType -> FatClusterLast\n", 0);
 
        return FatClusterLast;
    }
}

Referenced by _Requires_lock_held_(), and FatExamineFatEntries().

FatLogOf()

UCHAR FatLogOf

(

IN ULONG

Value

)

Definition at line 4655 of file allocsup.c.

{
    UCHAR Log = 0;
 
#if FASTFATDBG
    ULONG OrigValue = Value;
#endif
 
    PAGED_CODE();
 
    //
    //  Knock bits off until we we get a one at position 0
    //
 
    while ( (Value & 0xfffffffe) != 0 ) {
 
        Log++;
        Value >>= 1;
    }
 
    //
    //  If there was more than one bit set, the file system messed up,
    //  Bug Check.
    //
 
    if (Value != 0x1) {
 
        DebugTrace(+1, Dbg, "LogOf\n", 0);
        DebugTrace( 0, Dbg, "  Value = %8lx\n", OrigValue);
 
        DebugTrace( 0, Dbg, "Received non power of 2.\n", 0);
 
        DebugTrace(-1, Dbg, "LogOf -> %8lx\n", Log);
 
#ifdef _MSC_VER
#pragma prefast( suppress: 28159, "we bugcheck here because our internal data structures are seriously corrupted if this happens" )
#endif
        FatBugCheck( Value, Log, 0 );
    }
 
    return Log;
}

Referenced by FatSetupAllocationSupport().

FatLookupFatEntry()

VOID FatLookupFatEntry	(	IN PIRP_CONTEXT	IrpContext,
		IN PVCB	Vcb,
		IN ULONG	FatIndex,
		IN OUT PULONG	FatEntry,
		IN OUT PFAT_ENUMERATION_CONTEXT	Context
	)

Definition at line 3565 of file allocsup.c.

{
    PAGED_CODE();
 
    DebugTrace(+1, Dbg, "FatLookupFatEntry\n", 0);
    DebugTrace( 0, Dbg, "  Vcb      = %p\n", Vcb);
    DebugTrace( 0, Dbg, "  FatIndex = %4x\n", FatIndex);
    DebugTrace( 0, Dbg, "  FatEntry = %8lx\n", FatEntry);
 
    //
    //  Make sure they gave us a valid fat index.
    //
 
    FatVerifyIndexIsValid(IrpContext, Vcb, FatIndex);
 
    //
    //  Case on 12 or 16 bit fats.
    //
    //  In the 12 bit case (mostly floppies) we always have the whole fat
    //  (max 6k bytes) pinned during allocation operations.  This is possibly
    //  a wee bit slower, but saves headaches over fat entries with 8 bits
    //  on one page, and 4 bits on the next.
    //
    //  The 16 bit case always keeps the last used page pinned until all
    //  operations are done and it is unpinned.
    //
 
    //
    //  DEAL WITH 12 BIT CASE
    //
 
    if (Vcb->AllocationSupport.FatIndexBitSize == 12) {
 
        //
        //  Check to see if the fat is already pinned, otherwise pin it.
        //
 
        if (Context->Bcb == NULL) {
 
            FatReadVolumeFile( IrpContext,
                               Vcb,
                               FatReservedBytes( &Vcb->Bpb ),
                               FatBytesPerFat( &Vcb->Bpb ),
                               &Context->Bcb,
                               &Context->PinnedPage );
        }
 
        //
        //  Load the return value.
        //
 
 
        FatLookup12BitEntry( Context->PinnedPage, FatIndex, FatEntry );
 
    } else if (Vcb->AllocationSupport.FatIndexBitSize == 32) {
 
        //
        //  DEAL WITH 32 BIT CASE
        //
 
        ULONG PageEntryOffset;
        ULONG OffsetIntoVolumeFile;
 
        //
        //  Initialize two local variables that help us.
        //
        OffsetIntoVolumeFile = FatReservedBytes(&Vcb->Bpb) + FatIndex * sizeof(FAT_ENTRY);
        PageEntryOffset = (OffsetIntoVolumeFile % PAGE_SIZE) / sizeof(FAT_ENTRY);
 
        //
        //  Check to see if we need to read in a new page of fat
        //
 
        if ((Context->Bcb == NULL) ||
            (OffsetIntoVolumeFile / PAGE_SIZE != Context->VboOfPinnedPage / PAGE_SIZE)) {
 
            //
            //  The entry wasn't in the pinned page, so must we unpin the current
            //  page (if any) and read in a new page.
            //
 
            FatUnpinBcb( IrpContext, Context->Bcb );
 
            FatReadVolumeFile( IrpContext,
                               Vcb,
                               OffsetIntoVolumeFile & ~(PAGE_SIZE - 1),
                               PAGE_SIZE,
                               &Context->Bcb,
                               &Context->PinnedPage );
 
            Context->VboOfPinnedPage = OffsetIntoVolumeFile & ~(PAGE_SIZE - 1);
        }
 
        //
        //  Grab the fat entry from the pinned page, and return
        //
 
        *FatEntry = ((PULONG)(Context->PinnedPage))[PageEntryOffset] & FAT32_ENTRY_MASK;
 
    } else {
 
        //
        //  DEAL WITH 16 BIT CASE
        //
 
        ULONG PageEntryOffset;
        ULONG OffsetIntoVolumeFile;
 
        //
        //  Initialize two local variables that help us.
        //
 
        OffsetIntoVolumeFile = FatReservedBytes(&Vcb->Bpb) + FatIndex * sizeof(USHORT);
        PageEntryOffset = (OffsetIntoVolumeFile % PAGE_SIZE) / sizeof(USHORT);
 
        //
        //  Check to see if we need to read in a new page of fat
        //
 
        if ((Context->Bcb == NULL) ||
            (OffsetIntoVolumeFile / PAGE_SIZE != Context->VboOfPinnedPage / PAGE_SIZE)) {
 
            //
            //  The entry wasn't in the pinned page, so must we unpin the current
            //  page (if any) and read in a new page.
            //
 
            FatUnpinBcb( IrpContext, Context->Bcb );
 
            FatReadVolumeFile( IrpContext,
                               Vcb,
                               OffsetIntoVolumeFile & ~(PAGE_SIZE - 1),
                               PAGE_SIZE,
                               &Context->Bcb,
                               &Context->PinnedPage );
 
            Context->VboOfPinnedPage = OffsetIntoVolumeFile & ~(PAGE_SIZE - 1);
        }
 
        //
        //  Grab the fat entry from the pinned page, and return
        //
 
        *FatEntry = ((PUSHORT)(Context->PinnedPage))[PageEntryOffset];
    }
 
    DebugTrace(-1, Dbg, "FatLookupFatEntry -> (VOID)\n", 0);
    return;
}

Referenced by _Requires_lock_held_().

FatSelectBestWindow()

INLINE ULONG FatSelectBestWindow

(

IN PVCB

Vcb

)

Definition at line 279 of file allocsup.c.

{
    ULONG i, Fave = 0;
    ULONG MaxFree = 0;
    ULONG FirstEmpty = (ULONG)-1;
    ULONG ClustersPerWindow = MAX_CLUSTER_BITMAP_SIZE;
 
    NT_ASSERT( 1 != Vcb->NumberOfWindows);
 
    for (i = 0; i < Vcb->NumberOfWindows; i++) {
 
        if (Vcb->Windows[i].ClustersFree == ClustersPerWindow)  {
 
            if (-1 == FirstEmpty)  {
 
                //
                //  Keep note of the first empty window on the disc
                //
 
                FirstEmpty = i;
            }
        }
        else if (Vcb->Windows[i].ClustersFree > MaxFree)  {
 
            //
            //  This window has the most free clusters,  so far
            //
 
            MaxFree = Vcb->Windows[i].ClustersFree;
            Fave = i;
 
            //
            //  If this window has >50% free clusters,  then we will take it,
            //  so don't bother considering more windows.
            //
 
            if (MaxFree >= (ClustersPerWindow >> 1))  {
 
                break;
            }
        }
    }
 
    //
    //  If there were no windows with 50% or more freespace,  then select the
    //  first empty window on the disc,  if any - otherwise we'll just go with
    //  the one with the most free clusters.
    //
 
    if ((MaxFree < (ClustersPerWindow >> 1)) && (-1 != FirstEmpty))  {
 
        Fave = FirstEmpty;
    }
 
    return Fave;
}

Referenced by FatSetupAllocationSupport().

FatSetFatRun()

VOID FatSetFatRun	(	IN PIRP_CONTEXT	IrpContext,
		IN PVCB	Vcb,
		IN ULONG	StartingFatIndex,
		IN ULONG	ClusterCount,
		IN BOOLEAN	ChainTogether
	)

Definition at line 4139 of file allocsup.c.

{
#define MAXCOUNTCLUS 0x10000
#define COUNTSAVEDBCBS ((MAXCOUNTCLUS * sizeof(FAT_ENTRY) / PAGE_SIZE) + 2)
    PBCB SavedBcbs[COUNTSAVEDBCBS][2];
 
    ULONG SectorSize;
    ULONG Cluster;
 
    LBO StartSectorLbo;
    LBO FinalSectorLbo;
    LBO Lbo;
 
    PVOID PinnedFat;
 
    BOOLEAN ReleaseMutex = FALSE;
 
    ULONG SavedStartingFatIndex = StartingFatIndex;
 
    PAGED_CODE();
 
    DebugTrace(+1, Dbg, "FatSetFatRun\n", 0);
    DebugTrace( 0, Dbg, "  Vcb              = %p\n", Vcb);
    DebugTrace( 0, Dbg, "  StartingFatIndex = %8x\n", StartingFatIndex);
    DebugTrace( 0, Dbg, "  ClusterCount     = %8lx\n", ClusterCount);
    DebugTrace( 0, Dbg, "  ChainTogether    = %s\n", ChainTogether ? "TRUE":"FALSE");
 
    //
    //  Make sure they gave us a valid fat run.
    //
 
    FatVerifyIndexIsValid(IrpContext, Vcb, StartingFatIndex);
    FatVerifyIndexIsValid(IrpContext, Vcb, StartingFatIndex + ClusterCount - 1);
 
    //
    //  Check special case
    //
 
    if (ClusterCount == 0) {
 
        DebugTrace(-1, Dbg, "FatSetFatRun -> (VOID)\n", 0);
        return;
    }
 
    //
    //  Set Sector Size
    //
 
    SectorSize = 1 << Vcb->AllocationSupport.LogOfBytesPerSector;
 
    //
    //  Case on 12 or 16 bit fats.
    //
    //  In the 12 bit case (mostly floppies) we always have the whole fat
    //  (max 6k bytes) pinned during allocation operations.  This is possibly
    //  a wee bit slower, but saves headaches over fat entries with 8 bits
    //  on one page, and 4 bits on the next.
    //
    //  In the 16 bit case we only read one page at a time, as needed.
    //
 
    //
    //  DEAL WITH 12 BIT CASE
    //
 
    _SEH2_TRY {
 
        if (Vcb->AllocationSupport.FatIndexBitSize == 12) {
 
            //
            //  We read in the entire fat.  Note that using prepare write marks
            //  the bcb pre-dirty, so we don't have to do it explicitly.
            //
 
            RtlZeroMemory( &SavedBcbs[0][0], 2 * sizeof(PBCB) * 2);
 
            FatPrepareWriteVolumeFile( IrpContext,
                                       Vcb,
                                       FatReservedBytes( &Vcb->Bpb ),
                                       FatBytesPerFat( &Vcb->Bpb ),
                                       &SavedBcbs[0][0],
                                       &PinnedFat,
                                       TRUE,
                                       FALSE );
 
            //
            //  Mark the affected sectors dirty.  Note that FinalSectorLbo is
            //  the Lbo of the END of the entry (Thus * 3 + 2).  This makes sure
            //  we catch the case of a dirty fat entry straddling a sector boundry.
            //
            //  Note that if the first AddMcbEntry succeeds, all following ones
            //  will simply coalese, and thus also succeed.
            //
 
            StartSectorLbo = (FatReservedBytes( &Vcb->Bpb ) + StartingFatIndex * 3 / 2)
                             & ~(SectorSize - 1);
 
            FinalSectorLbo = (FatReservedBytes( &Vcb->Bpb ) + ((StartingFatIndex +
                             ClusterCount) * 3 + 2) / 2) & ~(SectorSize - 1);
 
            for (Lbo = StartSectorLbo; Lbo <= FinalSectorLbo; Lbo += SectorSize) {
 
                FatAddMcbEntry( Vcb, &Vcb->DirtyFatMcb, (VBO) Lbo, Lbo, SectorSize );
            }
 
            //
            //  Store the entries into the fat; we need a little
            //  synchonization here and can't use a spinlock since the bytes
            //  might not be resident.
            //
 
            FatLockFreeClusterBitMap( Vcb );
            ReleaseMutex = TRUE;
 
            for (Cluster = StartingFatIndex;
                 Cluster < StartingFatIndex + ClusterCount - 1;
                 Cluster++) {
 
                FatSet12BitEntry( PinnedFat,
                                  Cluster,
                                  ChainTogether ? Cluster + 1 : FAT_CLUSTER_AVAILABLE );
            }
 
            //
            //  Save the last entry
            //
 
            FatSet12BitEntry( PinnedFat,
                              Cluster,
                              ChainTogether ?
                              FAT_CLUSTER_LAST & 0xfff : FAT_CLUSTER_AVAILABLE );
 
            FatUnlockFreeClusterBitMap( Vcb );
            ReleaseMutex = FALSE;
 
        } else if (Vcb->AllocationSupport.FatIndexBitSize == 32) {
 
            //
            //  DEAL WITH 32 BIT CASE
            //
 
            for (;;) {
 
                VBO StartOffsetInVolume;
                VBO FinalOffsetInVolume;
 
                ULONG Page;
                ULONG FinalCluster;
                PULONG FatEntry = NULL;
                ULONG ClusterCountThisRun;
 
                StartOffsetInVolume = FatReservedBytes(&Vcb->Bpb) +
                                            StartingFatIndex * sizeof(FAT_ENTRY);
 
                if (ClusterCount > MAXCOUNTCLUS) {
                    ClusterCountThisRun = MAXCOUNTCLUS;
                } else {
                    ClusterCountThisRun = ClusterCount;
                }
 
                FinalOffsetInVolume = StartOffsetInVolume +
                                            (ClusterCountThisRun -  1) * sizeof(FAT_ENTRY);
 
                {
                    ULONG NumberOfPages;
                    ULONG Offset;
 
                    NumberOfPages = (FinalOffsetInVolume / PAGE_SIZE) -
                                    (StartOffsetInVolume / PAGE_SIZE) + 1;
 
                    RtlZeroMemory( &SavedBcbs[0][0], (NumberOfPages + 1) * sizeof(PBCB) * 2 );
 
                    for ( Page = 0, Offset = StartOffsetInVolume & ~(PAGE_SIZE - 1);
                          Page < NumberOfPages;
                          Page++, Offset += PAGE_SIZE ) {
 
                        FatPrepareWriteVolumeFile( IrpContext,
                                                   Vcb,
                                                   Offset,
                                                   PAGE_SIZE,
                                                   &SavedBcbs[Page][0],
                                                   (PVOID *)&SavedBcbs[Page][1],
                                                   TRUE,
                                                   FALSE );
 
                        if (Page == 0) {
 
                            FatEntry = (PULONG)((PUCHAR)SavedBcbs[0][1] +
                                                (StartOffsetInVolume % PAGE_SIZE));
                        }
                    }
                }
 
                //
                //  Mark the run dirty
                //
 
                StartSectorLbo = StartOffsetInVolume & ~(SectorSize - 1);
                FinalSectorLbo = FinalOffsetInVolume & ~(SectorSize - 1);
 
                for (Lbo = StartSectorLbo; Lbo <= FinalSectorLbo; Lbo += SectorSize) {
 
                    FatAddMcbEntry( Vcb, &Vcb->DirtyFatMcb, (VBO)Lbo, Lbo, SectorSize );
                }
 
                //
                //  Store the entries
                //
                //  We need extra synchronization here for broken architectures
                //  like the ALPHA that don't support atomic 16 bit writes.
                //
 
#ifdef ALPHA
                FatLockFreeClusterBitMap( Vcb );
                ReleaseMutex = TRUE;
#endif // ALPHA
 
                FinalCluster = StartingFatIndex + ClusterCountThisRun - 1;
                Page = 0;
 
                for (Cluster = StartingFatIndex;
                     Cluster <= FinalCluster;
                     Cluster++, FatEntry++) {
 
                    //
                    //  If we just crossed a page boundry (as opposed to starting
                    //  on one), update our idea of FatEntry.
 
                    if ( (((ULONG_PTR)FatEntry & (PAGE_SIZE-1)) == 0) &&
                         (Cluster != StartingFatIndex) ) {
 
                        Page += 1;
                        FatEntry = (PULONG)SavedBcbs[Page][1];
                    }
 
                    *FatEntry = ChainTogether ? (FAT_ENTRY)(Cluster + 1) :
                                                FAT_CLUSTER_AVAILABLE;
                }
 
                //
                //  Fix up the last entry if we were chaining together
                //
 
                if ((ClusterCount <= MAXCOUNTCLUS) &&
                    ChainTogether ) {
 
                    *(FatEntry-1) = FAT_CLUSTER_LAST;
                }
 
#ifdef ALPHA
                FatUnlockFreeClusterBitMap( Vcb );
                ReleaseMutex = FALSE;
#endif // ALPHA
 
                {
                    ULONG i;
 
                    //
                    //  Unpin the Bcbs
                    //
 
                    for (i = 0; (i < COUNTSAVEDBCBS) && (SavedBcbs[i][0] != NULL); i++) {
 
                        FatUnpinBcb( IrpContext, SavedBcbs[i][0] );
                        SavedBcbs[i][0] = NULL;
                    }
                }
 
                if (ClusterCount <= MAXCOUNTCLUS) {
 
                    break;
 
                } else {
 
                    StartingFatIndex += MAXCOUNTCLUS;
                    ClusterCount -= MAXCOUNTCLUS;
                }
            }
 
        } else {
 
            //
            //  DEAL WITH 16 BIT CASE
            //
 
            VBO StartOffsetInVolume;
            VBO FinalOffsetInVolume;
 
            ULONG Page;
            ULONG FinalCluster;
            PUSHORT FatEntry = NULL;
 
            StartOffsetInVolume = FatReservedBytes(&Vcb->Bpb) +
                                        StartingFatIndex * sizeof(USHORT);
 
            FinalOffsetInVolume = StartOffsetInVolume +
                                        (ClusterCount - 1) * sizeof(USHORT);
 
            //
            //  Read in one page of fat at a time.  We cannot read in the
            //  all of the fat we need because of cache manager limitations.
            //
            //  SavedBcb was initialized to be able to hold the largest
            //  possible number of pages in a fat plus and extra one to
            //  accomadate the boot sector, plus one more to make sure there
            //  is enough room for the RtlZeroMemory below that needs the mark
            //  the first Bcb after all the ones we will use as an end marker.
            //
 
            {
                ULONG NumberOfPages;
                ULONG Offset;
 
                NumberOfPages = (FinalOffsetInVolume / PAGE_SIZE) -
                                (StartOffsetInVolume / PAGE_SIZE) + 1;
 
                RtlZeroMemory( &SavedBcbs[0][0], (NumberOfPages + 1) * sizeof(PBCB) * 2 );
 
                for ( Page = 0, Offset = StartOffsetInVolume & ~(PAGE_SIZE - 1);
                      Page < NumberOfPages;
                      Page++, Offset += PAGE_SIZE ) {
 
                    FatPrepareWriteVolumeFile( IrpContext,
                                               Vcb,
                                               Offset,
                                               PAGE_SIZE,
                                               &SavedBcbs[Page][0],
                                               (PVOID *)&SavedBcbs[Page][1],
                                               TRUE,
                                               FALSE );
 
                    if (Page == 0) {
 
                        FatEntry = (PUSHORT)((PUCHAR)SavedBcbs[0][1] +
                                            (StartOffsetInVolume % PAGE_SIZE));
                    }
                }
            }
 
            //
            //  Mark the run dirty
            //
 
            StartSectorLbo = StartOffsetInVolume & ~(SectorSize - 1);
            FinalSectorLbo = FinalOffsetInVolume & ~(SectorSize - 1);
 
            for (Lbo = StartSectorLbo; Lbo <= FinalSectorLbo; Lbo += SectorSize) {
 
                FatAddMcbEntry( Vcb, &Vcb->DirtyFatMcb, (VBO) Lbo, Lbo, SectorSize );
            }
 
            //
            //  Store the entries
            //
            //  We need extra synchronization here for broken architectures
            //  like the ALPHA that don't support atomic 16 bit writes.
            //
 
#ifdef ALPHA
            FatLockFreeClusterBitMap( Vcb );
            ReleaseMutex = TRUE;
#endif // ALPHA
 
            FinalCluster = StartingFatIndex + ClusterCount - 1;
            Page = 0;
 
            for (Cluster = StartingFatIndex;
                 Cluster <= FinalCluster;
                 Cluster++, FatEntry++) {
 
                //
                //  If we just crossed a page boundry (as opposed to starting
                //  on one), update our idea of FatEntry.
 
                if ( (((ULONG_PTR)FatEntry & (PAGE_SIZE-1)) == 0) &&
                     (Cluster != StartingFatIndex) ) {
 
                    Page += 1;
                    FatEntry = (PUSHORT)SavedBcbs[Page][1];
                }
 
                *FatEntry = (USHORT) (ChainTogether ? (FAT_ENTRY)(Cluster + 1) :
                                                      FAT_CLUSTER_AVAILABLE);
            }
 
            //
            //  Fix up the last entry if we were chaining together
            //
 
            if ( ChainTogether ) {
 
#ifdef _MSC_VER
#pragma warning( suppress: 4310 )
#endif
                *(FatEntry-1) = (USHORT)FAT_CLUSTER_LAST;
 
            }
#ifdef ALPHA
            FatUnlockFreeClusterBitMap( Vcb );
            ReleaseMutex = FALSE;
#endif // ALPHA
        }
 
    } _SEH2_FINALLY {
 
        ULONG i;
 
        DebugUnwind( FatSetFatRun );
 
        //
        //  If we still somehow have the Mutex, release it.
        //
 
        if (ReleaseMutex) {
 
            NT_ASSERT( _SEH2_AbnormalTermination() );
 
            FatUnlockFreeClusterBitMap( Vcb );
        }
 
        //
        //  Unpin the Bcbs
        //
 
        for (i = 0; (i < COUNTSAVEDBCBS) && (SavedBcbs[i][0] != NULL); i++) {
 
            FatUnpinBcb( IrpContext, SavedBcbs[i][0] );
        }
 
        //
        //  At this point nothing in this finally clause should have raised.
        //  So, now comes the unsafe (sigh) stuff.
        //
 
        if ( _SEH2_AbnormalTermination() &&
            (Vcb->AllocationSupport.FatIndexBitSize == 32) ) {
 
            //
            //  Fat32 unwind
            //
            //  This case is more complex because the FAT12 and FAT16 cases
            //  pin all the needed FAT pages (128K max), after which it
            //  can't fail, before changing any FAT entries.  In the Fat32
            //  case, it may not be practical to pin all the needed FAT
            //  pages, because that could span many megabytes.  So Fat32
            //  attacks in chunks, and if a failure occurs once the first
            //  chunk has been updated, we have to back out the updates.
            //
            //  The unwind consists of walking back over each FAT entry we
            //  have changed, setting it back to the previous value.  Note
            //  that the previous value with either be FAT_CLUSTER_AVAILABLE
            //  (if ChainTogether==TRUE) or a simple link to the successor
            //  (if ChainTogether==FALSE).
            //
            //  We concede that any one of these calls could fail too; our
            //  objective is to make this case no more likely than the case
            //  for a file consisting of multiple disjoint runs.
            //
 
            while ( StartingFatIndex > SavedStartingFatIndex ) {
 
                StartingFatIndex--;
 
                FatSetFatEntry( IrpContext, Vcb, StartingFatIndex,
                    ChainTogether ?
                        StartingFatIndex + 1 : FAT_CLUSTER_AVAILABLE );
            }
        }
 
        DebugTrace(-1, Dbg, "FatSetFatRun -> (VOID)\n", 0);
    } _SEH2_END;
 
    return;
}

Referenced by FatSetFatRun().

FatSetupAllocationSupport()

VOID FatSetupAllocationSupport	(	IN PIRP_CONTEXT	IrpContext,
		IN PVCB	Vcb
	)

Definition at line 359 of file allocsup.c.

{
    ULONG BitIndex;
    ULONG ClustersDescribableByFat;
 
    PAGED_CODE();
 
    DebugTrace(+1, Dbg, "FatSetupAllocationSupport\n", 0);
    DebugTrace( 0, Dbg, "  Vcb = %p\n", Vcb);
 
    //
    //  Compute a number of fields for Vcb.AllocationSupport
    //
 
    Vcb->AllocationSupport.RootDirectoryLbo = FatRootDirectoryLbo( &Vcb->Bpb );
    Vcb->AllocationSupport.RootDirectorySize = FatRootDirectorySize( &Vcb->Bpb );
 
    Vcb->AllocationSupport.FileAreaLbo = FatFileAreaLbo( &Vcb->Bpb );
 
    Vcb->AllocationSupport.NumberOfClusters = FatNumberOfClusters( &Vcb->Bpb );
 
    Vcb->AllocationSupport.FatIndexBitSize = FatIndexBitSize( &Vcb->Bpb );
 
    Vcb->AllocationSupport.LogOfBytesPerSector = FatLogOf(Vcb->Bpb.BytesPerSector);
    Vcb->AllocationSupport.LogOfBytesPerCluster = FatLogOf(FatBytesPerCluster( &Vcb->Bpb ));
    Vcb->AllocationSupport.NumberOfFreeClusters = 0;
 
 
    //
    //  Deal with a bug in DOS 5 format, if the Fat is not big enough to
    //  describe all the clusters on the disk, reduce this number.  We expect
    //  that fat32 volumes will not have this problem.
    //
    //  Turns out this was not a good assumption.  We have to do this always now.
    //
 
    ClustersDescribableByFat = ( ((FatIsFat32(Vcb)? Vcb->Bpb.LargeSectorsPerFat :
                                                    Vcb->Bpb.SectorsPerFat) *
                                  Vcb->Bpb.BytesPerSector * 8)
                                 / FatIndexBitSize(&Vcb->Bpb) ) - 2;
 
    if (Vcb->AllocationSupport.NumberOfClusters > ClustersDescribableByFat) {
 
        Vcb->AllocationSupport.NumberOfClusters = ClustersDescribableByFat;
    }
 
    //
    //  Extend the virtual volume file to include the Fat
    //
 
    {
        CC_FILE_SIZES FileSizes;
 
        FileSizes.AllocationSize.QuadPart =
        FileSizes.FileSize.QuadPart = (FatReservedBytes( &Vcb->Bpb ) +
                                       FatBytesPerFat( &Vcb->Bpb ));
        FileSizes.ValidDataLength = FatMaxLarge;
 
        if ( Vcb->VirtualVolumeFile->PrivateCacheMap == NULL ) {
 
            FatInitializeCacheMap( Vcb->VirtualVolumeFile,
                                   &FileSizes,
                                   TRUE,
                                   &FatData.CacheManagerNoOpCallbacks,
                                   Vcb );
 
        } else {
 
            CcSetFileSizes( Vcb->VirtualVolumeFile, &FileSizes );
        }
    }
 
    _SEH2_TRY {
 
        if (FatIsFat32(Vcb) &&
            Vcb->AllocationSupport.NumberOfClusters > MAX_CLUSTER_BITMAP_SIZE) {
 
            Vcb->NumberOfWindows = (Vcb->AllocationSupport.NumberOfClusters +
                                    MAX_CLUSTER_BITMAP_SIZE - 1) /
                                   MAX_CLUSTER_BITMAP_SIZE;
 
        } else {
 
            Vcb->NumberOfWindows = 1;
        }
 
        Vcb->Windows = FsRtlAllocatePoolWithTag( PagedPool,
                                                 Vcb->NumberOfWindows * sizeof(FAT_WINDOW),
                                                 TAG_FAT_WINDOW );
 
        RtlInitializeBitMap( &Vcb->FreeClusterBitMap,
                             NULL,
                             0 );
 
        //
        //  Chose a FAT window to begin operation in.
        //
 
        if (Vcb->NumberOfWindows > 1) {
 
            //
            //  Read the fat and count up free clusters.  We bias by the two reserved
            //  entries in the FAT.
            //
 
            FatExamineFatEntries( IrpContext, Vcb,
                                  2,
                                  Vcb->AllocationSupport.NumberOfClusters + 2 - 1,
                                  TRUE,
                                  NULL,
                                  NULL);
 
 
            //
            //  Pick a window to begin allocating from
            //
 
            Vcb->CurrentWindow = &Vcb->Windows[ FatSelectBestWindow( Vcb)];
 
        } else {
 
            Vcb->CurrentWindow = &Vcb->Windows[0];
 
            //
            //  Carefully bias ourselves by the two reserved entries in the FAT.
            //
 
            Vcb->CurrentWindow->FirstCluster = 2;
            Vcb->CurrentWindow->LastCluster = Vcb->AllocationSupport.NumberOfClusters + 2 - 1;
        }
 
        //
        //  Now transition to the FAT window we have chosen.
        //
 
        FatExamineFatEntries( IrpContext, Vcb,
                              0,
                              0,
                              FALSE,
                              Vcb->CurrentWindow,
                              NULL);
 
        //
        //  Now set the ClusterHint to the first free bit in our favorite
        //  window (except the ClusterHint is off by two).
        //
 
        Vcb->ClusterHint =
            (BitIndex = RtlFindClearBits( &Vcb->FreeClusterBitMap, 1, 0 )) != -1 ?
                BitIndex + 2 : 2;
 
    } _SEH2_FINALLY {
 
        DebugUnwind( FatSetupAllocationSupport );
 
        //
        //  If we hit an exception, back out.
        //
 
        if (_SEH2_AbnormalTermination()) {
 
            FatTearDownAllocationSupport( IrpContext, Vcb );
        }
    } _SEH2_END;
 
    return;
}

Referenced by FatSetupAllocationSupport().

FatTearDownAllocationSupport()

VOID FatTearDownAllocationSupport	(	IN PIRP_CONTEXT	IrpContext,
		IN PVCB	Vcb
	)

Definition at line 549 of file allocsup.c.

{
    DebugTrace(+1, Dbg, "FatTearDownAllocationSupport\n", 0);
    DebugTrace( 0, Dbg, "  Vcb = %p\n", Vcb);
 
    PAGED_CODE();
 
    //
    //  If there are FAT buckets, free them.
    //
 
    if ( Vcb->Windows != NULL ) {
 
        ExFreePool( Vcb->Windows );
        Vcb->Windows = NULL;
    }
 
    //
    //  Free the memory associated with the free cluster bitmap.
    //
 
    if ( Vcb->FreeClusterBitMap.Buffer != NULL ) {
 
        ExFreePool( Vcb->FreeClusterBitMap.Buffer );
 
        //
        //  NULL this field as an flag.
        //
 
        Vcb->FreeClusterBitMap.Buffer = NULL;
    }
 
    //
    //  And remove all the runs in the dirty fat Mcb
    //
 
    FatRemoveMcbEntry( Vcb, &Vcb->DirtyFatMcb, 0, 0xFFFFFFFF );
 
    DebugTrace(-1, Dbg, "FatTearDownAllocationSupport -> (VOID)\n", 0);
 
    UNREFERENCED_PARAMETER( IrpContext );
 
    return;
}

Referenced by FatDeleteVcb(), and FatSetupAllocationSupport().