フラッシュファイルシステムの基礎と最適化技術

MS-FFS について

ここでは、Microsoft社が開発したバイト指向方式の MS-FFS (Microsoft Flash File System Media Control Structure) をもとにして、具体的な例を使いながら説明します。

MS-FFSでは、フラッシュメモリ上のすべてのイレーズブロックの最後にブロックアロケーションストラクチャ (Block Allocation Structure, BAS) という構造体を配置します。
BASは下図のような構造になっています。

struct BAS {
    struct AS {             // ┬
        byte Status;        // │
        byte Offset[3];     // │ 可変部
        word Len;           // │
    } Alloc[];              // ┼
    dword BootRecordPtr;    // │
    dword EraseCount;       // │
    word BlockSeq;          // │ 固定部
    word BlockSeqChecksum;  // │
    word Status;            // │
}                           // ┴

BASの固定部には、下記の各フィールドがあります。

• EraseCount : ブロックの消去回数を示すカウンタ
  • ブロックが消去されるごとにインクリメントされる。
  • フラッシュメモリが初期化された時点では、すべてのBASの EraseCount は 1 となっている。
• BlockSeq : ブロックの論理番号
  • このイレーズブロックの論理番号を保持している。
  • 各イレーズブロックは一意となるように論理番号がふられる。
• Status : ブロックのステータス
  • 現在のイレーズブロックの状態を示す。

また、可変部には配列Allocの要素であるアロケーションストラクチャ (Allocation Structure, AS) があり、下記の各フィールドを持っています。
この配列要素ASは、データ領域がイレーズブロックに割り当てる毎に1個、アドレスの下位に向かって追加されていきます。

• Status : 割り当てた領域のステータス
  • 割り当てた領域の現在の状態を示す。
• Offset : 割り当てた領域のオフセット
  • 割り当てた領域のイレーズブロックの先頭からのオフセット値。
• Len : 割り当てた領域のサイズ

フラッシュメモリをMS-FFSのフォーマットにしたがって初期化すると、各イレーズブロックは下図のような状態になります。

この状態からイレーズブロックにデータを書き込んでいきます。
フラッシュファイルシステムでは、イレーズブロックにデータを書き込む場合はアドレスの低い方から高い方に向かってバイト単位でつめて配置していきます。
データを書き込むためには領域を割り当て、1つの管理単位とします。
この領域を管理するために、BAS可変部である配列Allocの要素AS (以下、AS) を1つ生成します。
場所はBAS固定部からアドレスの低い方に向って配置します。 
この場合もバイト単位で行われます。この「バイト単位でつめて」というところからバイト指向方式と言われています。

例えば、33バイトのデータと25バイトのデータを順に書き込むと、下図のようになります。

領域とそれに対応するASの関連は矢印のように関連付けられます。
これは上記BAS構造図のOffsetとLenの2つのフィールドの情報によって行われます。

あと、先に説明しておかなければならないものとして、

• ディレクトリエントリストラクチャ (Directory Entry Structure, DirEntry)
• ファイルエントリストラクチャ (File Entry Structure, FileEntry)
• ファイルインフォストラクチャ (File Info Structure, FileInfo)

の3つの構造体があります。
それぞれ下図のような構造になっています。

また、ファイルのデータそのものを置く領域のことを、エクステント (Extent) といいます。

struct DirEntry {
    word Status;
    dword SiblingPtr;
    dword PrimaryPtr;
    dword SecondaryPtr;
    byte Attributes;
    word Time;
    word Date;
    word VarStructureLen;
    byte NameLen;
    byte Name[8];
    byte Ext[3];
}

struct FileEntry {
    word Status;
    dword SiblingPtr;
    dword PrimaryPtr;
    dword SecondaryPtr;
    byte Attributes;
    word Time;
    word Date;
    word VarStructureLen;
    byte NameLen;
    byte Name[8];
    byte Ext[3];
}

struct FileInfo {
    word Status;
    dword ExtentPtr;
    dword PrimaryPtr;
    dword SecondaryPtr;
    byte Attributes;
    word Time;
    word Date;
    word VarStructureLen;
    word UncompressedExtentLen;
    word CompressedExtentLen;
}

名前から分かるように、それぞれディレクトリ情報、ファイル情報、ファイルのデータの情報を管理する構造体となっています。
これらの構造体のうち説明に必要なフィールドは、

• Status : エントリのステータス
  • エントリの状態を示す。
• SiblingPtr : 次のエントリへのポインタ
  • 同一階層に存在するDirEntryもしくはFileEntryへのポインタ。
• PrimaryPtr : 次のエントリへのポインタ
  • DirEntryの場合は子階層のDirEntry、FileEntryへのポインタ。
  • FileEntryの場合はFileInfoへのポインタ。
• SecondaryPtr : 次のエントリへのポインタ
  • このエントリの最新版のエントリへのポインタ。

となっています。

エントリのポインタは4バイトのサイズで、上位2バイトが論理ブロック番号、下位2バイトがASのインデックスという構成になっています。
つまり、ポインタにはフラッシュメモリの物理アドレスは格納されないということです。
このようになっている理由はのちほど説明します。

ポインタの表記は便宜的に、
論理ブロック番号 : ASのインデックス
というようにします。
また、ヌルポインタを FNULL とします。

次ページ：イレーズブロックの構造化について

ページ: 1 2 3 4 5 6