679 lines
27 KiB
Plaintext
679 lines
27 KiB
Plaintext
///////////////////////////////////////////////////////////////////////////////
|
|
//
|
|
// Microsoft Research Singularity
|
|
//
|
|
// Copyright (c) Microsoft Corporation. All rights reserved.
|
|
//
|
|
// File: Fat16.sg
|
|
//
|
|
// NB Operations that modify the FAT table should be locked internally and
|
|
// should not expose any partial results. Read operations do not require
|
|
// locks.
|
|
//
|
|
|
|
using Microsoft.SingSharp;
|
|
using Microsoft.Singularity.Io;
|
|
using Microsoft.Singularity.Channels;
|
|
|
|
using System;
|
|
|
|
namespace Microsoft.Singularity.Services.Fat.Fs
|
|
{
|
|
internal sealed class Fat16 : Fat
|
|
{
|
|
Fat16Internal fatInternal;
|
|
|
|
internal Fat16(BlockCache! theBlockCache,
|
|
BpbSummary! theBpbSummary)
|
|
{
|
|
fatInternal = new Fat16Internal(theBlockCache, theBpbSummary);
|
|
}
|
|
|
|
internal override bool AllocateChain(int hintClusterArea,
|
|
int targetLength,
|
|
out int allocStart,
|
|
out int allocLength)
|
|
{
|
|
return fatInternal.AllocateChain(hintClusterArea, targetLength,
|
|
out allocStart, out allocLength);
|
|
}
|
|
|
|
internal override void FreeChain(int startCluster)
|
|
{
|
|
fatInternal.FreeChain(startCluster);
|
|
}
|
|
|
|
internal override bool GrowChain(BlockIndex! index,
|
|
int requestedExtensionLength,
|
|
out int actualExtensionLength)
|
|
{
|
|
return fatInternal.GrowChain(index, requestedExtensionLength,
|
|
out actualExtensionLength);
|
|
}
|
|
|
|
internal override void TruncateChain(BlockIndex! index,
|
|
int lengthInClusters)
|
|
{
|
|
fatInternal.TruncateChain(index, lengthInClusters);
|
|
}
|
|
|
|
internal override void PopulateIndex(BlockIndex! index,
|
|
int firstCluster)
|
|
{
|
|
fatInternal.PopulateIndex(index, firstCluster);
|
|
}
|
|
|
|
internal override bool CleanShutdown
|
|
{
|
|
get { return fatInternal.CleanShutdown; }
|
|
set { fatInternal.CleanShutdown = value; }
|
|
}
|
|
|
|
internal override bool HardError
|
|
{
|
|
get { return fatInternal.HardError; }
|
|
set { fatInternal.HardError = value; }
|
|
}
|
|
|
|
internal override int TotalClusters
|
|
{
|
|
get { return fatInternal.TotalClusters; }
|
|
}
|
|
|
|
internal override int EndOfChain
|
|
{
|
|
get { return fatInternal.EndOfChain; }
|
|
}
|
|
|
|
internal override int BadCluster
|
|
{
|
|
get { return fatInternal.BadCluster; }
|
|
}
|
|
|
|
// --------------------------------------------------------------------
|
|
// Internal representation of FAT16 structure
|
|
|
|
private sealed class Fat16Internal
|
|
{
|
|
private const int CleanShutdownMask = 0x8000;
|
|
private const int HardErrorMask = 0x4000;
|
|
internal const int UnallocatedMarker = 0x0000;
|
|
private const int EndOfChainMarker = 0xffff;
|
|
private const int EndOfChainMinimum = 0xffff;
|
|
private const int BadClusterMarker = 0xfff7;
|
|
internal const int MaxClusters = 0xfff7;
|
|
internal const int ReservedClusters = 2;
|
|
private const int EntryBytes = 2;
|
|
|
|
private BlockCache! blockCache;
|
|
private BpbSummary! bpbSummary;
|
|
private uint preferredFat;
|
|
private Bitmap! bitmap;
|
|
|
|
[ Microsoft.Contracts.NotDelayed ]
|
|
internal Fat16Internal(BlockCache! theBlockCache,
|
|
BpbSummary! theBpbSummary)
|
|
requires theBpbSummary.Version == FatVersion.Fat16;
|
|
requires theBpbSummary.SectorsPerFat >= 1;
|
|
requires theBpbSummary.NumberOfFats >= 1;
|
|
requires theBpbSummary.ClusterCount >= 1;
|
|
{
|
|
this.blockCache = theBlockCache;
|
|
this.bpbSummary = theBpbSummary;
|
|
this.preferredFat = 0;
|
|
this.bitmap = new Bitmap((int)theBpbSummary.ClusterCount
|
|
+ ReservedClusters);
|
|
base();
|
|
InitializeBitmap(this.preferredFat);
|
|
}
|
|
|
|
internal bool CleanShutdown
|
|
{
|
|
get {
|
|
int next;
|
|
GetNext(1, out next);
|
|
return (next & CleanShutdownMask) == CleanShutdownMask;
|
|
}
|
|
set {
|
|
int next, repl;
|
|
GetNext(1, out next);
|
|
if (value) {
|
|
repl = next | CleanShutdownMask;
|
|
}
|
|
else {
|
|
repl = next & ~CleanShutdownMask;
|
|
}
|
|
if (repl != next) {
|
|
SetNext(1, repl);
|
|
}
|
|
}
|
|
}
|
|
|
|
internal bool HardError
|
|
{
|
|
get {
|
|
int next;
|
|
GetNext(1, out next);
|
|
return (next & HardErrorMask) == HardErrorMask;
|
|
}
|
|
set {
|
|
int next, repl;
|
|
GetNext(1, out next);
|
|
if (value) {
|
|
repl = next | HardErrorMask;
|
|
}
|
|
else {
|
|
repl = next & ~HardErrorMask;
|
|
}
|
|
if (repl != next) {
|
|
SetNext(1, repl);
|
|
}
|
|
}
|
|
}
|
|
|
|
internal int TotalClusters
|
|
{
|
|
get {
|
|
return (int)bpbSummary.ClusterCount + ReservedClusters;
|
|
}
|
|
}
|
|
|
|
internal int EndOfChain
|
|
{
|
|
get { return EndOfChainMarker; }
|
|
}
|
|
|
|
internal int BadCluster
|
|
{
|
|
get { return BadClusterMarker; }
|
|
}
|
|
|
|
private int GetSector(uint fat, int cluster)
|
|
{
|
|
int byteOffset = EntryBytes * cluster;
|
|
return ((int)bpbSummary.FirstFatSector +
|
|
(int)(fat * bpbSummary.SectorsPerFat) +
|
|
byteOffset / (int)bpbSummary.BytesPerSector);
|
|
}
|
|
|
|
private int GetEntriesPerSector()
|
|
{
|
|
return (int)bpbSummary.BytesPerSector / EntryBytes;
|
|
}
|
|
|
|
private void ValidateClusterAssignment(int cluster,
|
|
ushort oldValue,
|
|
ushort newValue)
|
|
{
|
|
if (cluster < ReservedClusters) {
|
|
if (cluster == 1) {
|
|
const int ignoreMask = (CleanShutdownMask |
|
|
HardErrorMask);
|
|
assert(((int)oldValue & ~ignoreMask) ==
|
|
((int)newValue & ~ignoreMask));
|
|
return;
|
|
}
|
|
return;
|
|
}
|
|
|
|
if (oldValue >= EndOfChainMinimum &&
|
|
oldValue < EndOfChainMarker) {
|
|
oldValue = EndOfChainMarker;
|
|
}
|
|
|
|
assert (oldValue < TotalClusters ||
|
|
oldValue == BadCluster ||
|
|
oldValue == EndOfChainMarker);
|
|
|
|
assert (newValue < TotalClusters ||
|
|
newValue == BadCluster ||
|
|
newValue == EndOfChainMarker);
|
|
}
|
|
|
|
private void InitializeBitmap(uint fat)
|
|
{
|
|
int startSector = GetSector(fat, 0);
|
|
int endSector = startSector + (int)bpbSummary.SectorsPerFat;
|
|
int clustersPerSector = GetEntriesPerSector();
|
|
|
|
int cluster = 0;
|
|
for (int sector = startSector; sector != endSector; sector++) {
|
|
byte[]! in ExHeap buffer =
|
|
blockCache.BeginQuickBlockOperation((uint)sector);
|
|
int n = Math.Min(clustersPerSector,
|
|
TotalClusters - cluster);
|
|
|
|
for (int i = 0; i < n; i++, cluster++) {
|
|
ref short raw = ref buffer [i * EntryBytes];
|
|
short v = ByteOrder.LittleEndianToHost(raw);
|
|
if (v != UnallocatedMarker) {
|
|
int aStart, aLength;
|
|
bitmap.Allocate(cluster, 1,
|
|
out aStart, out aLength);
|
|
assert aStart == (int)cluster;
|
|
assert aLength == 1;
|
|
}
|
|
}
|
|
blockCache.EndQuickBlockOperation((uint)sector, buffer,
|
|
false);
|
|
}
|
|
|
|
// First two cluster entries are reserved. They
|
|
// should be set, but we check just in case since
|
|
// they are never valid.
|
|
for (int i = 0; i < ReservedClusters; i++) {
|
|
if (bitmap.GetFirstSetBitFrom(i) != i) {
|
|
int aStart, aLength;
|
|
bitmap.Allocate(i, 1, out aStart, out aLength);
|
|
assert aStart == i;
|
|
assert aLength == 1;
|
|
}
|
|
}
|
|
DumpFat("Initial Fat");
|
|
}
|
|
|
|
private void DumpFat(string! title)
|
|
{
|
|
DebugStub.Print("{0}\n", __arglist(title));
|
|
for (int i = ReservedClusters; i < TotalClusters; i++) {
|
|
int next;
|
|
GetNextInFat(0, i, out next);
|
|
if (next != 0) {
|
|
DebugStub.Print("Fat[{0:x8}] = {1:x8}\n",
|
|
__arglist(i, next));
|
|
}
|
|
|
|
for (uint fat = 1; fat < bpbSummary.NumberOfFats; fat++) {
|
|
int onext;
|
|
GetNextInFat(fat, i, out onext);
|
|
assert onext == next;
|
|
}
|
|
}
|
|
}
|
|
|
|
// ----------------------------------------------------------------
|
|
// Chain growth and creation related methods
|
|
|
|
internal bool GrowChain(BlockIndex! index,
|
|
int clustersToAdd,
|
|
out int clustersAdded)
|
|
requires index.Count > 0;
|
|
requires clustersToAdd > 0;
|
|
{
|
|
if (clustersToAdd > Bitmap.MaxAllocationLength) {
|
|
clustersToAdd = Bitmap.MaxAllocationLength;
|
|
}
|
|
|
|
lock (this) {
|
|
int tail;
|
|
if (index.Lookup(index.Count - 1, out tail) == false) {
|
|
assert false;
|
|
}
|
|
|
|
int newTailStart;
|
|
if (LockedAllocateChain(tail, clustersToAdd, index,
|
|
out newTailStart,
|
|
out clustersAdded)) {
|
|
SetNext(tail, newTailStart);
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
}
|
|
|
|
internal bool AllocateChain(int hintStart,
|
|
int length,
|
|
out int allocStart,
|
|
out int allocLength)
|
|
requires hintStart >= 0;
|
|
requires length > 0;
|
|
{
|
|
if (length > Bitmap.MaxAllocationLength) {
|
|
length = Bitmap.MaxAllocationLength;
|
|
}
|
|
|
|
lock (this) {
|
|
return LockedAllocateChain(hintStart, length, null,
|
|
out allocStart,
|
|
out allocLength);
|
|
}
|
|
}
|
|
|
|
private bool LockedAllocateChain(int tail,
|
|
int clustersToAdd,
|
|
BlockIndex index,
|
|
out int chainHead,
|
|
out int chainLength)
|
|
{
|
|
chainHead = tail;
|
|
chainLength = 0;
|
|
int chainTail = tail;
|
|
int request = Math.Min(Bitmap.MaxAllocationLength, clustersToAdd);
|
|
|
|
while (request != 0) {
|
|
int allocStart, allocLength;
|
|
if (bitmap.Allocate(chainTail, request,
|
|
out allocStart, out allocLength)) {
|
|
LockedWriteChain(allocStart, allocLength);
|
|
if (index != null) {
|
|
index.Append(allocStart, allocLength);
|
|
}
|
|
|
|
if (chainLength == 0) {
|
|
// First successful allocation - record chain head
|
|
chainHead = allocStart;
|
|
}
|
|
else {
|
|
// Subsequent allocation - link into chain
|
|
SetNext(chainTail, allocStart);
|
|
}
|
|
|
|
chainTail = allocStart + allocLength - 1;
|
|
chainLength += allocLength;
|
|
request = Math.Min(Bitmap.MaxAllocationLength,
|
|
clustersToAdd - chainLength);
|
|
}
|
|
else {
|
|
request /= 2;
|
|
}
|
|
}
|
|
return chainLength > 0;
|
|
}
|
|
|
|
private void LockedWriteChain(int chainStart,
|
|
int chainLength)
|
|
{
|
|
for (uint i = 0; i < bpbSummary.NumberOfFats; i++) {
|
|
LockedWriteChainInFat(i, chainStart, chainLength);
|
|
}
|
|
}
|
|
|
|
private void LockedWriteChainInFat(uint fat,
|
|
int chainStart,
|
|
int chainLength)
|
|
requires chainStart >= ReservedClusters;
|
|
requires chainStart < this.TotalClusters;
|
|
requires (chainStart + chainLength <
|
|
this.TotalClusters);
|
|
requires chainLength != 0;
|
|
{
|
|
int entriesPerSector = GetEntriesPerSector();
|
|
ushort lastMarker = EndOfChainMarker;
|
|
int entryStart = chainStart % entriesPerSector;
|
|
|
|
if (entryStart + chainLength > entriesPerSector) {
|
|
int skip = entriesPerSector - entryStart;
|
|
LockedWriteChainInFat(fat,
|
|
chainStart + skip,
|
|
chainLength - skip);
|
|
chainLength = skip;
|
|
assert (chainStart + skip) < MaxClusters;
|
|
lastMarker = (ushort)(chainStart + skip);
|
|
DebugStub.Assert((lastMarker % entriesPerSector) == 0);
|
|
}
|
|
|
|
int sector = GetSector(fat, chainStart);
|
|
|
|
byte[]! in ExHeap blockData =
|
|
blockCache.BeginQuickBlockOperation((uint)sector);
|
|
|
|
ushort oldCluster, newCluster;
|
|
for (int i = 0; i < chainLength - 1; i++) {
|
|
int offset = EntryBytes * (entryStart + i);
|
|
ref ushort rawCluster = ref blockData[offset];
|
|
oldCluster = ByteOrder.LittleEndianToHost(rawCluster);
|
|
newCluster = (ushort)(chainStart + i + 1);
|
|
ValidateClusterAssignment(chainStart + i,
|
|
oldCluster, newCluster);
|
|
rawCluster = ByteOrder.HostToLittleEndian(newCluster);
|
|
}
|
|
|
|
int entryEnd = entryStart + chainLength - 1;
|
|
ref ushort theCluster =
|
|
ref blockData[EntryBytes * (int)entryEnd];
|
|
oldCluster = ByteOrder.LittleEndianToHost(theCluster);
|
|
newCluster = lastMarker;
|
|
ValidateClusterAssignment(chainStart + chainLength - 1,
|
|
oldCluster, newCluster);
|
|
theCluster = ByteOrder.HostToLittleEndian(newCluster);
|
|
|
|
blockCache.EndQuickBlockOperation((uint)sector, blockData,
|
|
true);
|
|
}
|
|
|
|
// ----------------------------------------------------------------
|
|
// Chain truncation and deletion related methods
|
|
|
|
internal void TruncateChain(BlockIndex! index,
|
|
int clusterLength)
|
|
requires clusterLength >= 0 && clusterLength < index.Count;
|
|
ensures index.Count == clusterLength;
|
|
{
|
|
if (clusterLength == index.Count) {
|
|
return;
|
|
}
|
|
|
|
if (clusterLength == 0) {
|
|
int headCluster;
|
|
if (index.Lookup(0, out headCluster) == false) {
|
|
assert false;
|
|
}
|
|
FreeChain(headCluster);
|
|
index.TruncateToLength(clusterLength);
|
|
return;
|
|
}
|
|
|
|
int newTail;
|
|
if (index.Lookup(clusterLength - 1, out newTail) == false) {
|
|
assert false;
|
|
}
|
|
|
|
int zap;
|
|
if (index.Lookup(clusterLength, out zap) == false) {
|
|
assert false;
|
|
}
|
|
|
|
lock (this) {
|
|
SetNext(newTail, EndOfChainMarker);
|
|
LockedFreeChain(zap);
|
|
}
|
|
index.TruncateToLength(clusterLength);
|
|
}
|
|
|
|
internal void FreeChain(int startCluster)
|
|
requires (startCluster >= ReservedClusters &&
|
|
startCluster < MaxClusters);
|
|
{
|
|
lock (this) {
|
|
LockedFreeChain(startCluster);
|
|
}
|
|
}
|
|
|
|
private void LockedFreeChain(int startCluster)
|
|
requires (startCluster >= ReservedClusters &&
|
|
startCluster < MaxClusters);
|
|
{
|
|
bool updateBitmap = true;
|
|
for (uint i = 0; i < bpbSummary.NumberOfFats; i++) {
|
|
LockedFreeChainInFat(i, startCluster, updateBitmap);
|
|
updateBitmap = false;
|
|
}
|
|
}
|
|
|
|
private void LockedFreeChainInFat(uint fat,
|
|
int cluster,
|
|
bool updateBitmap)
|
|
requires cluster >= ReservedClusters && cluster < MaxClusters;
|
|
{
|
|
int sector = GetSector(fat, cluster);
|
|
int entriesPerSector = GetEntriesPerSector();
|
|
|
|
byte []! in ExHeap blockData =
|
|
blockCache.BeginQuickBlockOperation((uint)sector);
|
|
|
|
for (;;) {
|
|
int byteOffset =
|
|
EntryBytes * (cluster % entriesPerSector);
|
|
ref ushort rawCluster = ref blockData [byteOffset];
|
|
ushort oldValue = ByteOrder.LittleEndianToHost(rawCluster);
|
|
ushort newValue = (ushort)UnallocatedMarker;
|
|
|
|
ValidateClusterAssignment(cluster, oldValue, newValue);
|
|
rawCluster = ByteOrder.HostToLittleEndian(newValue);
|
|
|
|
if (updateBitmap) {
|
|
bitmap.Free(cluster, 1);
|
|
}
|
|
|
|
cluster = (ushort)oldValue;
|
|
|
|
if (cluster >= MaxClusters) {
|
|
break;
|
|
}
|
|
|
|
int nextSector = GetSector(fat, cluster);
|
|
if (nextSector != sector) {
|
|
blockCache.EndQuickBlockOperation((uint)sector,
|
|
blockData,
|
|
true);
|
|
sector = nextSector;
|
|
blockData =
|
|
blockCache.BeginQuickBlockOperation((uint)sector);
|
|
}
|
|
}
|
|
blockCache.EndQuickBlockOperation((uint)sector, blockData,
|
|
true);
|
|
}
|
|
|
|
// ----------------------------------------------------------------
|
|
// Populate
|
|
|
|
private void PopulateIndexFromFat(uint fat,
|
|
BlockIndex! index,
|
|
int firstCluster)
|
|
requires firstCluster >= Fat16Internal.ReservedClusters;
|
|
requires index.Count == 0;
|
|
{
|
|
int cluster = firstCluster;
|
|
|
|
int sector = GetSector(fat, cluster);
|
|
int entriesPerSector = GetEntriesPerSector();
|
|
|
|
byte []! in ExHeap blockData =
|
|
blockCache.BeginQuickBlockOperation((uint)sector);
|
|
|
|
for (;;) {
|
|
index.Append(cluster);
|
|
|
|
int byteOffset = EntryBytes * (cluster % entriesPerSector);
|
|
ref ushort rawCluster = ref blockData [byteOffset];
|
|
// TODO: Check cluster is not bad
|
|
cluster = (int)ByteOrder.HostToLittleEndian(rawCluster);
|
|
if (cluster < ReservedClusters || cluster >= MaxClusters) {
|
|
break;
|
|
}
|
|
|
|
int nextSector = GetSector(fat, cluster);
|
|
if (nextSector != sector) {
|
|
blockCache.EndQuickBlockOperation((uint)sector,
|
|
blockData,
|
|
false);
|
|
sector = nextSector;
|
|
blockData =
|
|
blockCache.BeginQuickBlockOperation((uint)sector);
|
|
}
|
|
|
|
}
|
|
blockCache.EndQuickBlockOperation((uint)sector, blockData,
|
|
false);
|
|
}
|
|
|
|
internal void PopulateIndex(BlockIndex! index,
|
|
int firstCluster)
|
|
requires firstCluster >= Fat16Internal.ReservedClusters;
|
|
requires index.Count == 0;
|
|
{
|
|
PopulateIndexFromFat(this.preferredFat, index, firstCluster);
|
|
}
|
|
|
|
// ----------------------------------------------------------------
|
|
// Single link traversal and modification methods
|
|
|
|
private bool GetNext(int cluster, out int next)
|
|
{
|
|
assert cluster < TotalClusters;
|
|
|
|
for (uint i = 0; i < bpbSummary.NumberOfFats; i++) {
|
|
try {
|
|
GetNextInFat(preferredFat, cluster, out next);
|
|
return true;
|
|
}
|
|
catch (Exception e) {
|
|
DebugStub.WriteLine("Caught {0}", __arglist(e.ToString()));
|
|
}
|
|
preferredFat =
|
|
(preferredFat + 1) % bpbSummary.NumberOfFats;
|
|
}
|
|
|
|
assert false;
|
|
next = 0;
|
|
return false;
|
|
// XXX: Fatal error could not read Fat entry
|
|
}
|
|
|
|
private void GetNextInFat(uint fat, int cluster, out int next)
|
|
{
|
|
int entriesPerSector = GetEntriesPerSector();
|
|
int sector = GetSector(fat, cluster);
|
|
|
|
byte[]! in ExHeap blockData =
|
|
blockCache.BeginQuickBlockOperation((uint)sector);
|
|
int offset = EntryBytes * (cluster % entriesPerSector);
|
|
ref ushort rawPointer = ref blockData[offset];
|
|
next = ByteOrder.LittleEndianToHost(rawPointer);
|
|
blockCache.EndQuickBlockOperation((uint)sector, blockData,
|
|
false);
|
|
|
|
// Fix the out value so even
|
|
// non-MS formatted filesystems appear to show the
|
|
// same EOC marker. NB First two clusters are not used
|
|
// and their next pointers may have special purposes.
|
|
if (cluster >= ReservedClusters && next >= EndOfChainMinimum) {
|
|
next = EndOfChainMarker;
|
|
}
|
|
}
|
|
|
|
private void SetNext(int cluster, int next)
|
|
{
|
|
assert cluster < TotalClusters;
|
|
assert ((next < TotalClusters) ||
|
|
(next >= BadClusterMarker && next <= EndOfChainMarker) ||
|
|
(cluster < ReservedClusters));
|
|
|
|
for (uint i = 0; i < bpbSummary.NumberOfFats; i++) {
|
|
SetNextInFat(i, cluster, next);
|
|
}
|
|
}
|
|
|
|
private void SetNextInFat(uint fat, int cluster, int next)
|
|
{
|
|
int sector = GetSector(fat, cluster);
|
|
int entryOffset =
|
|
EntryBytes * (cluster % GetEntriesPerSector());
|
|
|
|
byte[]! in ExHeap blockData =
|
|
blockCache.BeginQuickBlockOperation((uint)sector);
|
|
|
|
ref ushort rawCluster = ref blockData[entryOffset];
|
|
ushort oldCluster = ByteOrder.LittleEndianToHost(rawCluster);
|
|
ushort newCluster = (ushort)next;
|
|
ValidateClusterAssignment(cluster, oldCluster, newCluster);
|
|
rawCluster = ByteOrder.HostToLittleEndian(newCluster);
|
|
|
|
blockCache.EndQuickBlockOperation((uint)sector, blockData,
|
|
true);
|
|
}
|
|
} // class Fat16Internal
|
|
} // class Fat16
|
|
} // namespace Microsoft.Singularity.Services.Fat.Fs
|