(57)【特許請求の範囲】
【請求項１】
フラッシュメモリのデータの記録場所を示すアドレス情報を有する第１の管理テーブルを格納する手段と、
前記フラッシュメモリの記録データの中で有効なデータを示す情報を有する第２の管理テーブルを格納する手段と、
前記第２の管理テーブルに基づいて、アドレス単位で前記有効なデータをカウントして得られる有効なデータ数を有するカウンタテーブルを作成する手段と、
前記カウンタテーブルを格納するカウンタテーブル格納手段と、
前記第１の管理テーブルを参照して取得されるアドレス単位の有効なデータ数と、前記カウンタテーブルを参照して取得されるアドレス単位の有効なデータ数とを比較し、当該比較結果に基づいて前記第１及び第２の管理テーブルの整合性を確認する整合性確認処理を実行するコントローラと
を具備するデータ記憶装置。
【請求項２】
前記コントローラは、前記整合性確認処理として、
前記カウンタテーブルを使用して、第１の管理テーブルを参照して取得される有効なデータ数と前記第２の管理テーブルを参照して取得される有効なデータ数とを比較し、当該比較結果が一致であれば正常終了する第１の処理と、
前記比較結果が不一致であれば、不整合のデータ位置を特定する第２の処理と
を実行するように構成されている請求項１に記載のデータ記憶装置。
【請求項３】
前記第１の管理テーブルは、第１のデータ単位で前記データの記録場所を管理するための前記アドレス情報を有し、
前記アドレス情報は、第１のデータ単位のアドレスを示す第１のアドレス及び前記フラッシュメモリのデータ消去単位の第２のアドレスを含み、
前記第２の管理テーブルは、前記第１のデータ単位で有効なデータを示す情報を有し、
前記カウンタテーブルは、前記第２のアドレス毎の前記有効なデータ数を有する請求項１または請求項２のいずれか１項に記載のデータ記憶装置。
【請求項４】
前記第２の管理テーブルは、前記第２のアドレス毎に前記第１のデータ単位のデータの有効と無効を示す情報を有する請求項３に記載のデータ記憶装置。
【請求項５】
前記第１の管理テーブルは、クラスタ単位のデータの記録場所を示す正引きテーブルであり、
前記第２の管理テーブルは、前記クラスタ単位でデータの有効と無効を示す有効クラスタビットマップテーブルであり、
前記カウンタテーブルは、前記第２の管理テーブルで有効を示す有効クラスタ数をアドレス単位でカウントしたカウント値を有する有効クラスタ数カウンタテーブルであり、
前記コントローラは、
前記カウンタテーブルを使用して、前記第１の管理テーブルと前記第２の管理テーブルとの間で有効クラスタ数が一致するか否かを確認する処理を実行するように構成されている請求項１に記載のデータ記憶装置。
【請求項６】
前記コントローラは、前記整合性確認処理として、
前記第１の管理テーブルを参照して確認された有効クラスタ数と前記カウンタテーブルから取得されるカウント値とを比較し、当該比較結果が一致であれば正常終了する第１の処理と、
前記比較結果が不一致であれば、前記第１の管理テーブルと前記第２の管理テーブルとの間で不整合な不整合クラスタ位置を特定する第２の処理と
を実行するように構成されている請求項５に記載のデータ記憶装置。
【請求項７】
前記コントローラは、前記第１の処理として、
前記第１の管理テーブルにエントリされているクラスタに対応する前記第２の管理テーブルのクラスタが有効または無効であるかを判断し、
前記判断結果が有効であれば前記カウンタテーブルのカウント値をデクリメントし、
前記第１の管理テーブルの全てのエントリに対する前記カウント値のデクリメント結果がゼロであれば、前記第１及び第２の管理テーブルの有効クラスタ数の一致を確認する処理を実行するように構成されている請求項６に記載のデータ記憶装置。
【請求項８】
フラッシュメモリのデータの記録場所を示すアドレス情報を有する第１の管理テーブル、及び前記フラッシュメモリの記録データの中で有効なデータを示す情報を有する第２の管理テーブルを有するデータ記憶装置に適用するテーブル管理方法であって、
前記第２の管理テーブルに基づいて、アドレス単位で前記有効なデータをカウントして得られる有効なデータ数を有するカウンタテーブルを作成し、
前記第１の管理テーブルを参照して取得されるアドレス単位の有効なデータ数と、前記カウンタテーブルを参照して取得されるアドレス単位の有効なデータ数とを比較し、
前記比較結果に基づいて前記第１及び第２の管理テーブルの整合性を確認する整合性確認処理を実行するテーブル管理方法。
【請求項９】
前記整合性確認処理として、
前記カウンタテーブルを使用して、第１の管理テーブルを参照して取得される有効なデータ数と、前記第２の管理テーブルを参照して取得される有効なデータ数とを比較し、
前記比較結果が一致であれば正常終了し、
前記比較結果が不一致であれば、不整合のデータ位置を特定する請求項８に記載のテーブル管理方法。
【請求項１０】
前記第１の管理テーブルは、クラスタ単位のデータの記録場所を示す正引きテーブルであり、
前記第２の管理テーブルは、前記クラスタ単位でデータの有効と無効を示す有効クラスタビットマップテーブルであり、
前記カウンタテーブルは、前記第２の管理テーブルで有効を示す有効クラスタ数をアドレス単位でカウントしたカウント値を有する有効クラスタ数カウンタテーブルであり、
前記整合性確認処理として、
前記カウンタテーブルを使用して、前記第１の管理テーブルと前記第２の管理テーブルとの間で有効クラスタ数が一致するか否かを確認する請求項８に記載のテーブル管理方法。
【請求項１１】
前記整合性確認処理として、
前記第１の管理テーブルを参照して確認された有効クラスタ数と前記カウンタテーブルから取得されるカウント値とを比較し、
前記比較結果が一致であれば正常終了し、
前記比較結果が不一致であれば、前記第１の管理テーブルと前記第２の管理テーブルとの間で不整合な不整合クラスタ位置を特定する請求項１０に記載のテーブル管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、不揮発性メモリを記憶媒体とするデータ記憶装置に関する。
【背景技術】
【０００２】
近年、データ記憶装置として、書き換え可能な不揮発性メモリであるNAND型フラッシュメモリ（以下、単にフラッシュメモリと表記する場合がある）を記憶媒体とするＳＳＤ（solid state drive）の開発が推進されている。
【０００３】
ＳＳＤコントローラは、フラッシュメモリに対してデータのリード／ライト動作を制御する場合に、各種のデータ管理テーブルを使用する。データ管理テーブルは、例えば物理ブロックと論理ブロックとの対応関係を示すテーブルや、記録データの中で最新のデータを示すテーブルなどが含まれる。
【０００４】
ところで、ＳＳＤでは、例えば宇宙放射線を要因としてハードエラーが発生することが周知である。このハードエラーにより、ＳＳＤコントローラの内部メモリで保持しているデータ管理テーブルにビットエラーが発生することがある。このため、ＳＳＤコントローラでは、データ管理テーブルに含まれる各テーブル間で不整合が発生する可能性がある。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００９−２１１２３２号公報
【特許文献２】特開２００９−２４４９６２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従来のＳＳＤでは、ＳＳＤコントローラの内部メモリで保持しているデータ管理テーブルは、ハードエラーにより不整合が発生する可能性がある。このため、ＳＳＤは、通常のデータのリード／ライト動作以外に、データ管理テーブルに対する整合性の確認処理を行なう必要がある。この整合性の確認処理は、リード／ライト動作を実行していない時間に行なう必要があるため、高速性が要求される。
【０００７】
そこで、本発明の目的は、データ管理テーブルに対する整合性の確認処理を高速に行なことが可能なデータ記憶装置を提供することにある。
【課題を解決するための手段】
【０００８】
実施形態によれば、データ記憶装置は、第１の管理テーブルを格納する手段と、第２の管理テーブルを格納する手段と、カウンタテーブルを作成する手段と、カウンタテーブル格納手段と、コントローラとを具備する。前記第１の管理テーブルは、フラッシュメモリのデータの記録場所を示すアドレス情報を有する。前記第２の管理テーブルは、前記フラッシュメモリの記録データの中で有効なデータを示す情報を有する。前記カウンタテーブルを作成する手段は、前記第２の管理テーブルに基づいてアドレス単位で前記有効なデータをカウントして得られる有効なデータ数を有するカウンタテーブルを作成する。前記カウンタテーブル格納手段は前記カウンタテーブルを格納する。前記コントローラは、前記第１の管理テーブルを参照して取得されるアドレス単位の有効なデータ数と、前記カウンタテーブルを参照して取得されるアドレス単位の有効なデータ数とを比較し、当該比較結果に基づいて前記第１及び第２の管理テーブルの整合性を確認する整合性確認処理を実行する。
【図面の簡単な説明】
【０００９】
【図１】実施形態に関するＳＳＤの構成を説明するためのブロック図。
【図２】実施形態に関する有効クラスタビットマップテーブルのフォーマット例を示す図。
【図３】実施形態に関する有効クラスタ数カウンタテーブルのフォーマット例を示す図。
【図４】実施形態に関するＶＰＮのフォーマット例を示す図。
【図５】実施形態に関する正引きテーブルのフォーマット例を示す図。
【図６】実施形態に関する正引きテーブルエントリのマジックナンバーの一例を示す図。
【図７】実施形態に関するテーブル整合チェック処理を説明するためのフローチャート。
【図８】他の実施形態に関するＳＳＤの構成を説明するためのブロック図。
【発明を実施するための形態】
【００１０】
以下図面を参照して、実施形態を説明する。
【００１１】
［データ記憶装置の構成］
図１は、本実施形態に関するＳＳＤ（solid state drive）の構成を説明するためのブロック図である。図１に示すように、ＳＳＤは大別して、フラッシュメモリコントローラ（以下、ＳＳＤコントローラと表記する場合がある）１０と、NAND型フラッシュメモリ（以下、単にフラッシュメモリと表記する場合がある）１１とを有する。フラッシュメモリ１１は、主としてユーザデータを記憶するためのデータ記憶媒体である。
【００１２】
ＳＳＤコントローラ１０は、インターフェース１２と、コントローラ１３と、第１のテーブル相関位置決定モジュール１４と、第１テーブルデータ解析モジュール１５と、第２テーブルデータ解析モジュール１６と、第２テーブル有効性判定モジュール１７と、第３テーブル生成モジュール１８と、第３テーブル更新モジュール１９とを有する。
【００１３】
さらに、ＳＳＤコントローラ１０は、テーブル管理モジュール２０と、第２のテーブル相関位置決定モジュール２１と、テーブル整合結果通知モジュール２２と、第２テーブル複製生成モジュール２３と、第２テーブル複製更新モジュール２４と、第３テーブル解析モジュール２５とを有する。また、ＳＳＤコントローラ１０は、第１テーブル格納部２６と、第２テーブル格納部２７と、第２テーブル複製格納部２８と、第３テーブル格納部２９とを有する。
【００１４】
インターフェース１２は、図示しないチャネルを介してフラッシュメモリ１１と接続し、リード／ライト動作に必要なコマンドやデータの入出力を行なう。チャネル（Ｃｈ）とは、データの入出力を行なう伝送経路である。チャネル（Ｃｈ）は例えば１６チャネルを有し、最大１６個のデータを同時に伝送可能である。コントローラ１３は、バスを介して接続した各モジュール１４〜２５の動作を制御する。
【００１５】
テーブル管理モジュール２０は、第１テーブル格納部２６、第２テーブル格納部２７、第２テーブル複製格納部２８および第３テーブル格納部２９のそれぞれに格納される各種テーブルへの問い合わせ、及びデータ更新等のテーブルアクセスを管理する。第１テーブル格納部２６、第２テーブル格納部２７、第２テーブル複製格納部２８および第３テーブル格納部２９はそれぞれ、ＤＲＡＭなどのメモリ（記憶デバイス）からなる。
【００１６】
第１テーブル格納部２６は、後述する正引きテーブルを格納する。第２テーブル格納部２７は、後述する有効クラスタビットマップテーブル（以下、有効クラスタテーブルと表記する場合がある）を格納する。第２テーブル複製格納部２８は、後述するように、有効クラスタテーブルの１エントリのコピー（複製）を格納する。第３テーブル格納部２９は、後述する有効クラスタ数カウンタテーブル（以下、カウンタテーブルと表記する場合がある）を格納する。
【００１７】
第１のテーブル相関位置決定モジュール１４は、第１テーブル格納部２６に格納された正引きテーブルの１エントリに基づいて、前記正引きテーブルエントリに対応する第２テーブル格納部２７に格納された有効クラスタテーブルのエントリ位置を決定する。第２のテーブル相関位置決定モジュール２１は、第２テーブル複製格納部２８に格納された有効クラスタテーブルの１エントリのコピーのビット位置に基づいて、前記有効クラスタテーブルエントリのビット位置に対応する第１テーブル格納部２６に格納された正引きテーブルのエントリ位置を決定する。
【００１８】
第１テーブルデータ解析モジュール１５は、第１テーブル格納部２６に格納された正引きテーブルのエントリデータを解析する。テーブル整合結果通知モジュール２２は、該正引きテーブルおよび該有効クラスタテーブルの整合性の結果を通知する。即ち、当該モジュール２２は、正引きテーブルおよび有効クラスタテーブルのいずれか一方では有効であって、かつ他方では無効となっているクラスタのＬＣＡ（後述する論理オフセットアドレス）を上位システム（図示しないＣＰＵ）に通知する。ＣＰＵでは、ＳＳＤの全体的制御を司るファームウェア（ＦＷ）が実行される。
【００１９】
第２テーブルデータ解析モジュール１６は、第２テーブル格納部２７に格納された有効クラスタテーブルのエントリデータを解析する。第２テーブル複製生成モジュール２３は、第２テーブル格納部２７に格納された有効クラスタテーブルの１エントリのコピー（複製）を生成し、第２テーブル複製格納部２８に格納する。
【００２０】
第２テーブル有効性判定モジュール１７は、第１テーブル格納部２６に格納された正引きテーブルの参照により有効とされたクラスタが、第２テーブル格納部２７に格納された有効クラスタテーブル上で有効か否かを判定する。第２テーブル複製更新モジュール２４は、第２テーブル複製格納部２８に格納された有効クラスタテーブルのコピー（複製）により生成されたエントリデータを更新する。
【００２１】
第３テーブル生成モジュール１８は、カウンタテーブルを新規に生成し、第３テーブル格納部２９に格納する。第３テーブルデータ解析モジュール２５は、第３テーブル格納部２９に格納されたカウンタテーブルのエントリデータを解析する。第３テーブルデータ更新モジュール１９は、第３テーブル格納部２９に格納されたカウンタテーブルのエントリデータを更新する。
【００２２】
（定義）
本実施形態のＳＳＤに関係する用語の定義を説明する。
【００２３】
まず、物理ページとは、フラッシュメモリ１１の内部で、一括してリード／ライトが可能な単位である。論理ページは、ＳＳＤ内で設定されるリード／ライトの単位である。１論理ページは、１またはそれ以上の物理ページに対応付けられている。
【００２４】
物理ブロックは、フラッシュメモリ１１の内部で、独立してデータ消去可能な最小単位である。物理ブロックは複数の物理ページからなる。論理ブロックは、ＳＳＤ内で設定されるデータ消去単位である。１論理ブロックは、１またはそれ以上の物理ページに対応付けられている。
【００２５】
セクタは、ＳＳＤをアクセスするホストシステム（例えばパーソナルコンピュータ）からの最小アクセス単位である。クラスタは、ＳＳＤ内でデータを管理する管理単位である。１クラスタは、例えば８セクタに対応付けられる。また、クラスタサイズの２以上の整数倍が論理ページサイズに対応付けられる。
【００２６】
有効クラスタは、最新のデータを保持しているクラスタである。無効クラスタは、最新ではないデータを保持しているクラスタである。コンパクション（compaction）とは、管理対象内の論理ブロックから有効クラスタを取り出して、新しい論理ブロックに書き直す処理を意味する。
【００２７】
プレーン（以下、ＰＬと略す場合がある）は、同一のフラッシュメモリチップ内において、同時アクセス可能な領域（district）を意味する。本実施形態では、２プレーンに分割されている。但し、分割数は、２に限定されるものではなく、任意に設定される。
【００２８】
論理ブロックＩＤ（以下、ＬＢＩＤと略す場合がある）は、論理ブロックを識別するために各論理ブロックに付加された番号である。
【００２９】
有効クラスタビットマップは、論理ブロックで記録されているデータが有効または無効であるかを、クラスタ単位で“１”（有効）と“０”（無効）のビットマップで示すデータである。有効クラスタビットマップテーブル（有効クラスタテーブル）は、有効クラスタビットマップを管理するテーブルである。有効クラスタテーブルは、例えば図２に示すような構成である。
【００３０】
有効クラスタ数カウンタは、論理ブロックに記録されているデータの中で有効クラスタの数（有効クラスタ数）を示すデータ（カウント値）である。有効クラスタ数カウンタは、コンパクション時にコンパクション対象を選択する際に使用されるデータである。有効クラスタ数カウンタテーブル（カウンタテーブル）は、有効クラスタ数カウンタを論理ブロックＩＤをキーとしたテーブルである。本実施形態では、カウンタテーブルは、図３に示すようなフォーマットからなり、論理ブロックＩＤ（ＬＢＩＤ）をインデックスとした配列として実現する。
【００３１】
さらに、ＬＣＡは、論理ブロックアドレス（ＬＢＡ）を３ビット右にシフトして得られる値を意味する。ＶＰＮは、仮想ページ番号を意味する。ＶＰＮは、図４に示すように、物理ブロック内の物理ページ番号PAGENO、フラッシュメモリチップ内のプレーン番号ＰＬ、およびチャネル番号CHNOからなる。
【００３２】
論理クラスタアドレスは、フラッシュメモリ上の論理的なクラスタアドレスである。論理クラスタアドレスは、論理ブロックＩＤ（ＬＢＩＤ）、仮想ページ番号（ＶＰＮ）、および物理ページ内のクラスタオフセット（Ｃ）により表現される。正引きテーブルは、フラッシュメモリ上でのクラスタ単位で論理的なデータ記録場所を管理するテーブルである。本実施形態は、図５に示すように、ＬＣＡをインデックスとして、ＬＢＩＤ、ＶＰＮ、Ｃからなるエントリデータを要素とする値の配列として実現する。なお、図５において、Ｐはパリティビットを意味する。
【００３３】
図６は、正引きテーブルエントリのマジックナンバーの一例を示す図である。マジックナンバーは、正引きテーブルエントリのパリティビット（Ｐ）以外のビットが全て“１”の場合である。これは、対応するＬＣＡに含まれる全てのセクタが、ＳＳＤの起動後に唯の一回もデータの書き込みがなされていないことを意味する。
【００３４】
（テーブル整合チェック処理）
以下、図７のフローチャートを参照して、本実施形態のテーブル整合チェック処理を説明する。
【００３５】
本実施形態では、コントローラ１３は、各モジュール１４〜２５の動作を制御することにより、正引きテーブルと有効クラスタビットマップテーブル（有効クラスタテーブル）の整合性チェック処理を実行する。
【００３６】
前述したように、正引きテーブルは、第１テーブル格納部２６に格納されるテーブルであり、第１の管理テーブルと表記する場合がある。また、有効クラスタテーブルは、第２テーブル格納部２７に格納されるテーブルであり、第２の管理テーブルと表記する場合がある。
【００３７】
本実施形態では、整合性チェック処理中は、第１の管理テーブル及び第２の管理テーブルを更新する処理が並列に動作しないことが条件である。また、１回の整合性チェック処理において、検出可能な不整合箇所は１箇所である。テーブル整合結果通知モジュール２２は、１つの不整合を検出した段階で、当該検出箇所と共に整合結果をＣＰＵに通知する。
【００３８】
まず、第３テーブル生成モジュール１８は、論理ブロック（ＬＢＩＤ）毎に第２テーブル格納部２７に格納された有効クラスタテーブルから、クラスタ単位で有効“１”のデータをカウントして、有効クラスタ数カウンタテーブル（カウンタテーブル）を作成する（ブロック１００）。第３テーブル生成モジュール１８は、作成したカウンタテーブルを第３の管理テーブルとして、第３テーブル格納部２９に格納する。
【００３９】
ここで、有効クラスタテーブルは、図２に示すように、クラスタ単位で有効を“１”で示し、無効を“０”で示すビットマップを示すテーブルである。また、カウンタテーブルは、図３に示すように、論理ブロック（ＬＢＩＤ）毎の有効クラスタ数を示すデータからなるテーブルである。
【００４０】
次に、コントローラ１３は、作成されたカウンタテーブル（第３の管理テーブル）を使用して、正引きテーブル（第１の管理テーブル）の全エントリについて、整合チェック処理を実行する（ブロック１０１〜１０８のループ）。ここで、ブロック１０８は、処理ループの終了を示す。
【００４１】
具体的には、第１のテーブル相関位置決定モジュール１４は、テーブル管理モジュール２０に対して、ＬＣＡ順に第１テーブル格納部２６に格納された正引きテーブルへの参照を要求し、論理クラスタアドレス(ＬＮＣＡ)を取得する（ブロック１０２）。ＬＮＣＡは、図５に示すように、論理ブロックＩＤ（ＬＢＩＤ）、仮想ページ番号（ＶＰＮ）、および物理ページ内のクラスタオフセット（Ｃ）からなる。
【００４２】
第１テーブルデータ解析モジュール１５は、取得されたＬＮＣＡに含まれるＬＢＩＤの有効性をチェックする（ブロック１０３）。このチェックにより、当該ＬＮＣＡがマジックナンバーの場合には、次の処理対象であるＬＮＣＡの取得を実行する（ブロック１０３のＹＥＳ）。マジックナンバーは、正引きテーブルエントリのパリティビット（Ｐ）以外のビットが全て“１”の場合である。この場合、ＬＣＡに含まれる全てのセクタが唯の一回もデータの書き込みがなされていないことを意味する。
【００４３】
一方、マジックナンバーではない場合でＬＮＣＡが範囲外の場合には、テーブル整合結果通知モジュール２２は、当該ＬＣＡから算出される論理ブロックアドレス（ＬＢＡ）を取得し、上位システムであるＣＰＵにエラーと共に返却して終了する（ブロック１０４のＹＥＳ，１２４）。
【００４４】
ＬＮＣＡが範囲内の場合には、第２テーブルデータ解析モジュール１６は、テーブル管理モジュール２０を介して、有効クラスタテーブル（第２の管理テーブル）の当該物理クラスタのビット値を取得する（ブロック１０５）。第２テーブル有効性判定モジュール１７は、物理クラスタのビット値を用いて、有効クラスタテーブルの当該物理クラスタが有効または無効のいずれであるかをチェックする（ブロック１０６）。
【００４５】
このチェック結果が無効クラスタの場合には、テーブル整合結果通知モジュール２２は、当該ＬＣＡから算出される論理ブロックアドレス（ＬＢＡ）を取得し、上位システムであるＣＰＵにエラーと共に返却して終了する（ブロック１０６のＹＥＳ，１２４）。チェック結果が有効クラスタの場合には、第３テーブル更新モジュール１９は、第３の管理テーブル（カウンタテーブル）上の当該論理ブロック（ＬＢＩＤ）のカウント値（有効クラスタ数）を１デクリメントする（ブロック１０７）。
【００４６】
コントローラ１３は、全ての正引きテーブルエントリについてのチェック処理の完了後（ブロック１０１〜１０８のループ終了後）に、次の処理に移行する。即ち、第３テーブルデータ解析モジュール２５は、第３の管理テーブル（カウンタテーブル）のエントリを先頭からチェックする（ブロック１０９，１１０）。このチェック結果によりエントリ値がゼロであれば、第３テーブルデータ解析モジュール２５は次のエントリのチェックに進む（ブロック１１０のＹＥＳ，１１１）。
【００４７】
エントリ値がゼロでなければ、第３テーブルデータ解析モジュール２５は、当該エントリ値であるＬＢＩＤを第２テーブル複製生成モジュール２３に渡す（ブロック１１０のＮＯ）。第２テーブル複製生成モジュール２３は、テーブル管理モジュール２０に対して、対応する有効クラスタテーブルの参照要求を行なう。第２テーブル複製生成モジュール２３は、有効クラスタテーブルから取得した当該ビットマップデータを第２テーブル複製格納部２８に格納する（ブロック１１２）。即ち、第２テーブル複製格納部２８には、第２テーブル格納部２７に格納された有効クラスタテーブルの１エントリのコピーが格納される。
【００４８】
テーブル整合結果通知モジュール２２は、第２テーブル複製格納２８にデータ、即ち有効クラスタテーブルの１エントリのコピーが格納されていない場合には、エラーが検出されなかったとして、上位システムであるＣＰＵに返却して終了する（ブロッ１１３のＹＥＳ，１１４）。
【００４９】
一方、コピーが格納されている場合には、第１のテーブル相関位置決定モジュール１４は、テーブル管理モジュール２０に対して、ＬＣＡ順に第１テーブル格納部２６に格納された正引きテーブルへの参照を要求し、論理クラスタアドレス(ＬＮＣＡ)を取得する（ブロック１１５，１１６）。
【００５０】
第１テーブルデータ解析モジュール１５は、取得されたＬＮＣＡに含まれるＬＢＩＤの有効性をチェックする（ブロック１１７）。このチェックは、当該ＬＮＣＡがマジックナンバーであるか否かを判定する。または、ＬＢＩＤが第２テーブル複製格納部２８に格納された（ただ一つの）有効クラスタビットマップデータのＬＢＩＤと一致するか否かを判定する。このチェックにより、当該ＬＮＣＡがマジックナンバーの場合には、次の処理対象であるＬＮＣＡの取得を実行する（ブロック１１７のＹＥＳ，１１９）。チェック結果がＬＢＩＤの不一致の場合には、同様に、次の処理対象であるＬＮＣＡの取得を実行する（ブロック１１７のＹＥＳ，１１９）。
【００５１】
一方、判定条件が成立しない場合、即ちＬＢＩＤが一致する場合には、第２テーブルデータ解析モジュール１６は、第２テーブル複製格納部２８に格納された有効クラスタのビットマップデータの該当ビット位置を算出する（ブロック１１７のＮＯ）。第２テーブル複製更新モジュール２４は、該当有効クラスタのビットを落とす（ブロック１１８）。
【００５２】
コントローラ１３は、全ての正引きテーブルエントリについてのチェック処理の完了後（ブロック１１５〜１１９のループ終了後）に、次の処理に移行する。即ち、第２テーブルデータ解析モジュール１６は、第２テーブル複製格納部２８に格納された有効クラスタのビットマップデータの“１”の値をとるビット位置を検索する（ブロック１２０）。
【００５３】
テーブル整合結果通知モジュール２２は、第２テーブルデータ解析モジュール１６の検索により、“１”の値をとるビットが存在しない場合には、処理中にビット化けが発生したエラーとして、上位システムであるＣＰＵに返却して終了する（ブロック１２１のＹＥＳ，１２２）。
【００５４】
ここで、第２テーブル複製格納部２８にコピーされた時点では、当該有効クラスタのビットマップが示す論理ブロックには、正引きテーブル上では無効とされ、有効クラスタテーブル上では有効とされる物理クラスタが存在すると判定されている。従って、ビット位置の検索処理の時点では（ブロック１２０）、当該有効クラスタテーブル上には“１”の値をとるビットが存在するはずである。しかし、データにビット化けが発生していた場合、該有効クラスタのビットマップデータには、“１”の値をとるビットが含まれていない可能性がある。このように、ブロック１２１のＹＥＳ，１２２の処理は前記ビット化けが発生したことにより、これ以上処理を進めることが不可能となったことを上位システムであるＣＰＵに通知する処理である。
【００５５】
一方、第２テーブルデータ解析モジュール１６は、検索により“１”の値をとるビットが存在する場合には、テーブル整合結果通知モジュール２２に正引きテーブルから算出したＬＮＣＡと一致したエントリのＬＣＡを渡す。即ち、第２のテーブル相関位置決定モジュール２１は、“１”であるビット位置（複数ある場合は、最もLSB側に位置するビット）に対応するＬＮＣＡを有効クラスタテーブルから算出し、前記ＬＮＣＡと一致するエントリを正引きテーブルから検索し、検索の結果得られたエントリに対応するキーのＬＣＡの値をテーブル整合結果通知部２２に渡する。テーブル整合結果通知部２２は、当該ＬＣＡから算出される論理ブロックアドレス（ＬＢＡ）を取得し、上位システムであるＣＰＵにエラーと共に返却して終了する（ブロック１２１のＮＯ，１２３，１２４）。
【００５６】
以上のように本実施形態の整合性チェック処理であれば、正引きテーブル（第１の管理テーブル）と有効クラスタビットマップテーブル（第２の管理テーブル）の整合性を、第３の管理テーブルである有効クラスタ数カウンタテーブル（カウンタテーブル）を使用して実行する。
【００５７】
本実施形態の整合性チェック処理の要点は、カウンタテーブル上に記録された物理ブロック単位での有効クラスタ数と、正引きテーブルから読み込む有効性のあるクラスタ（登録されている物理クラスタアドレス）の数を物理ブロックごとにカウントして比較を行なう点にある。即ち、正引きテーブルの有効クラスタに対応する有効クラスタテーブルの物理クラスタが、有効または無効であるかを判断する。無効であれば、この時点で不整合があること、および不整合箇所の特定までができることになる。有効であれば、カウンタテーブルのカウンタ値（有効クラスタ数）からデクリメントする（ブロック１０１〜１０８のループ処理）。この結果として、両テーブル（正引きテーブルと有効クラスタテーブル）の有効クラスタ数が一致すれば、整合性チェックは正常終了となる（ブロック１１１，１１４）。一方、両テーブルの有効クラスタ数が不一致であれば、不整合クラスタ位置の特定処理に移行する（ブロック１１５〜１２４）。
【００５８】
このような２段階による整合性チェック処理により、整合性チェックの結果が正常であれば不整合クラスタ位置の特定処理を省略できるため、全体として処理ステップ数を相対的に減少し、高速に行なうことが可能となる。また、整合性チェック処理に必要なメモリ容量を最小限にできるため、ＳＳＤに搭載するメモリ容量が相対的に少ない場合でも整合性チェック処理を実現することができる。これにより、ＳＳＤにおいて、ハードエラーに伴うデータ管理テーブルのエラー発生の解析を容易に行なうことが可能となる。
【００５９】
（変形例）
本実施形態の整合性チェック処理において、１回の整合性チェックにおいて、検出可能な不整合箇所を１箇所であることを前提として説明したが、これに限ることなく、１回の整合性チェックにおいて、複数箇所の不整合箇所を検出することも可能である。
【００６０】
本変形例は、第２テーブル複製格納部２８に格納する有効クラスタテーブルのエントリデータである物理ブロック単位のビットマップを１つに制限するのではなく、図７のブロック１１０の条件に合致する全ての有効クラスタテーブルのエントリデータである物理ブロック単位のビットマップを格納する構成とする。これにより、１回の整合性チェックにおいて、複数物理ブロックの不整合を検出することも可能となる。
【００６１】
［他の実施形態］
図８は、他の実施形態に関するＳＳＤの構成を説明するためのブロック図である。
【００６２】
上記実施形態は、前述したように、有効クラスタ数カウンタテーブル（第３の管理テーブル）を作成する構成である（ブロック１００を参照）。これに対して、本実施形態は、当該カウンタテーブルを予め用意し、これを利用して整合性チェック処理を実行する構成である。有効クラスタ数カウンタテーブルにおける各エントリ値をＳＳＤシステムとして常に正しい状態に維持するための、当該テーブルの更新タイミングとしては、フラッシュメモリ１１に記録されたユーザデータの有効／無効の状態が変化するタイミング、すなわちユーザデータをフラッシュメモリ１１に書き込む際、ユーザデータをフラッシュメモリ１１から消去する際、もしくはコンパクション実施にともなうユーザデータの物理的格納場所の移動のタイミングが望ましい。前記タイミングで有効クラスタ数カウンタテーブルを更新することにより、有効クラスタ数カウンタテーブルをＳＳＤにおける他の処理、例えばコンパクション処理の際に、コンパクション処理対象となる有効クラスタ数が最小の論理ブロックを選択するための情報に利用することが可能となる、というメリットがある。本実施形態はＳＳＤが前記望ましいタイミングでのテーブル更新を実施することを前提とする。
【００６３】
具体的には、図８に示すように、第３テーブル生成モジュール１８を、第３テーブル複製生成モジュール３０に変更する。第３テーブル更新部１９を、第３テーブル複製更新モジュール３１に変更する。第３テーブルデータ解析モジュール２５を、第３テーブル複製データ解析モジュール３２に変更する。さらに、テーブル管理モジュール２０が管理するテーブル格納部として、第３テーブル複製格納部３３を追加する。
【００６４】
また、本実施形態では、第３テーブル格納部２９は、既存の有効クラスタ数カウンタテーブル（カウンタテーブル）を格納する。第３テーブル複製格納部３３は、第３テーブル格納部２９に格納されたカウンタテーブル全体のコピー（複製）を格納する。前記カウンタテーブル全体のコピーを格納するのは、本実施形態における整合性チェック処理において実施されるカウンタテーブルのエントリ値の更新処理により、オリジナルのカウンタテーブルが破壊されるのを避けるためである。第３テーブル複製生成モジュール３０は、第３テーブル格納部２９に格納されたカウンタテーブル全体を第３テーブル複製格納部３３にコピーする。
【００６５】
第３テーブル複製データ解析モジュール３２は、第３テーブル複製格納部３３に格納されたカウンタテーブルのエントリデータを解析する。第３テーブル複製更新モジュール３１は、第３テーブル複製格納部３３に格納されたカウンタテーブルのエントリデータを更新する。
【００６６】
本実施形態の構成であれば、既存の有効カウンタテーブルを使用する場合には、第３テーブル複製生成モジュール３０により、第３テーブル格納部２９に格納されたカウンタテーブル全体を第３テーブル複製格納部３３にコピーする。このコピーデータに対して参照または更新を行なうことにより、整合性チェック処理を実行する。この場合、カウンタテーブルのエントリから有効を示す“１”の値をカウントする処理を、エントリ値のコピー処理に置き換えることになり、処理全体が簡素化される。
【００６７】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００６８】
１０…フラッシュメモリコントローラ（ＳＳＤコントローラ）、
１１…NAND型フラッシュメモリ（フラッシュメモリ）、１２…インターフェース、
１３…コントローラ、１４…第１のテーブル相関位置決定モジュール、
１５…第１テーブルデータ解析モジュール、１６…第２テーブルデータ解析モジュール、
１７…第２テーブル有効性判定モジュール、１８…第３テーブル生成モジュール、
１９…第３テーブル更新モジュール、２０…テーブル管理モジュール、
２１…第２のテーブル相関位置決定モジュール、
２２…テーブル整合結果通知モジュール、２３…第２テーブル複製生成モジュール、
２４…第２テーブル複製更新モジュール、２５…第３テーブル解析モジュール、
２６…第１テーブル格納部、２７…第２テーブル格納部、
２８…第２テーブル複製格納部、２９…第３テーブル格納部、
３０…第３テーブル複製生成モジュール、３１…第３テーブル複製更新モジュール、
３２…第３テーブル複製データ解析モジュール、３３…第３テーブル複製格納部。
【図１】
0005330432.tif 000002
【図２】
0005330432.tif 000003
【図３】
0005330432.tif 000004
【図４】
0005330432.tif 000005
【図５】
0005330432.tif 000006
【図６】
0005330432.tif 000007
【図７】
0005330432.tif 000008
【図８】
0005330432.tif 000009