(57)【要約】【課題】不揮発性メモリ（ＮＶＭ）を有するシステムの論理的ブロックアドレス（ＬＢＡ）ビットマップ使用のためのシステム及び方法を提供する。【解決手段】システムの揮発性メモリにビットマップが記憶され、このビットマップは、１つ以上の論理的アドレスのマッピング状態を記憶することができる。ビットマップを使用することで、システムは、ＮＶＭにアクセスする必要なく、ＬＢＡのマッピング状態を決定することができる。更に、システムは、最小限のＮＶＭアクセスでＬＢＡのマッピング状態を更新することができる。ＮＶＭアクセスの回数を減少することにより、システムは、ガーベージコレクションプロセスをトリガーすることを回避でき、全体的なシステム性能を改善することができる。【選択図】図１
2013137770.tif 000002
【特許請求の範囲】
【請求項１】
不揮発性メモリ（ＮＶＭ）を備えた電子装置の論理的ブロックアドレス（ＬＢＡ）をアンマップする方法であって、
前記電子装置のコントロール回路を使用して、揮発性メモリに記憶されたビットマップに複数のＬＢＡのマッピング状態を記憶する処理と、
前記コントロール回路を使用して、第１のＬＢＡをアンマップする要求をファイルシステムから受信する処理と、
前記コントロール回路を使用して、前記第１のＬＢＡのマッピング状態を、前記ビットマップを更新するだけでアンマップへと変更する処理と、
前記コントロール回路を使用して、前記第１のＬＢＡに対応するスーパーブロックのための有効性カウンタを減少する処理と、
が実行される方法。
【請求項２】
前記ビットマップの各エントリは、１つのＬＢＡ及び複数のＬＢＡの一方に対応する、請求項１に記載の方法。
【請求項３】
前記コントロール回路を使用して、前記ファイルシステムからシステムブートアップ中に前記複数のＬＢＡのマッピング状態に関連した情報を受信する処理を更に含む、請求項１又は２に記載の方法。
【請求項４】
前記コントロール回路を使用して、前記ＮＶＭをスキャンすることにより前記複数のＬＢＡのマッピング状態を得る処理を更に含む、請求項１又は２に記載の方法。
【請求項５】
前記コントロール回路を使用して、第２のＬＢＡを読み取るための読み取り要求を前記ファイルシステムから受信する処理と、
前記コントロール回路を使用して、前記第２のＬＢＡに関連したビットマップのエントリを調べる処理と、
前記コントロール回路を使用して、前記第２のＬＢＡがアンマップされたことを前記エントリが示すかどうか決定する処理と、
前記第２のＬＢＡがアンマップされたことを前記エントリが示すとの決定に応答して、前記コントロール回路を使用して、前記第２のＬＢＡが関連ユーザデータをもたないことを指示する情報を前記ファイルシステムに送信する処理と、が更に実行される、請求項１又は２に記載の方法。
【請求項６】
前記第２のＬＢＡがアンマップされないことを前記エントリが示すとの決定に応答して、前記コントロール回路を使用して、前記ＮＶＭのインデックスページを調べて、前記第２のＬＢＡに関連したユーザデータの位置を求める処理と、
前記コントロール回路を使用して、前記ユーザデータを前記ファイルシステムへ送信する処理と、
が更に実行される、請求項５に記載の方法。
【請求項７】
不揮発性メモリ（ＮＶＭ）と、
揮発性メモリと、
を備え、前記揮発性メモリは、
前記ＮＶＭの複数のスーパーブロックに関連した複数の有効性カウンタ、
複数のエントリを含むツリーであって、前記ＮＶＭの物理的アドレスと複数の論理的ブロックアドレス（ＬＢＡ）との間のマッピングを与えるツリー、
前記複数のＬＢＡのマッピング状態を記憶するためのビットマップ、及び
メモリインターフェイスであって、
前記複数のＬＢＡのうちのあるＬＢＡをアンマップする要求を受信し、
前記ビットマップを調べて、ＬＢＡがアンマップされたかどうか決定し、
ＬＢＡがアンマップされないとの決定に応答して、ビットマップにおいてＬＢＡをアンマップし、
前記ツリーを調べることにより前記複数の有効性カウンタのうちの少なくとも１つを更新し、
ツリーメモリの使用が更新で減少する場合だけ前記アンマップされたＬＢＡを反映するように前記ツリーを更新する、
ように動作するコントロール回路を含むメモリインターフェイスと、
を備えたシステム。
【請求項８】
前記コントロール回路は、
前記ＬＢＡに対応するツリーのエントリの位置を算出し、
前記ＬＢＡに関連したエントリの物理的アドレスを所定のトークン値へ更新する、
ように動作する請求項７に記載のシステム。
【請求項９】
前記コントロール回路は、ツリーを更新すると、ツリーの合計エントリ数の正味の減少を生じると決定するように動作する、請求項７又は８に記載のシステム。
【請求項１０】
前記ＬＢＡがアンマップされるとの決定に応答して、前記コントロール回路は、ＬＢＡが既にアンマップされていることを示す情報を前記ファイルシステムへ送信するように動作する、請求項７又は８に記載のシステム。
【請求項１１】
前記コントロール回路は、
前記ＬＢＡに対応するツリーのエントリの位置を算出し、
前記エントリを使用して前記ＬＢＡに関連したデータを記憶するスーパーブロックを決定し、
前記スーパーブロックに関連した前記複数の有効性カウンタのうちのある有効性カウンタをデクリメントする、
ように動作する請求項７又は８に記載のシステム。
【請求項１２】
前記ビットマップの各エントリは複数のＬＢＡに対応する、請求項７又は８に記載のシステム。
【請求項１３】
前記コントロール回路は、
前記ビットマップのエントリのマッピング状態が未知の状態であると決定し、
ツリー及び少なくともインデックスページの少なくとも一方を調べて、前記エントリに関連した各ＬＢＡのマッピング状態を決定する、
ように動作する請求項１２に記載のシステム。
【請求項１４】
前記コントロール回路は、
前記ビットマップの各エントリが１つのＬＢＡに対応するように前記ビットマップを初期化し、
未知の状態をもつ前記ビットマップのエントリの数が所定のスレッシュホールド未満である場合に前記ビットマップの各エントリに対応するＬＢＡの数を増加する、
ように動作する請求項７又は８に記載のシステム。
【請求項１５】
前記コントロール回路は、前記ビットマップの各エントリが所定数のＬＢＡに対応するように前記ビットマップを初期化するよう動作する、請求項７又は８に記載のシステム。
【請求項１６】
不揮発性メモリ（ＮＶＭ）のインデックスページにアクセスするためのメモリインターフェイスであって、
複数の論理的ブロックアドレス（ＬＢＡ）のうちのあるＬＢＡをアンマップする要求を受信し、
揮発性メモリに記憶されたビットマップにおいて前記ＬＢＡをアンマップし、
揮発性メモリに記憶されたツリーが前記ＬＢＡに対応する論理的−物理的マッピングを含むかどうか決定し、
前記ツリーが前記ＬＢＡに対応する論理的−物理的マッピングを含むとの決定に応答して、前記ＬＢＡに関連したインデックスページをＮＶＭからロードする、
ように動作するコントロール回路を備えたメモリインターフェイス。
【請求項１７】
前記コントロール回路は、前記インデックスページをインデックステーブルキャッシュへロードするように動作する、請求項１６に記載のメモリインターフェイス。
【請求項１８】
前記コントロール回路は、
前記ロードされたインデックスページを調べることにより前記ＬＢＡに関連したＮＶＭのスーパーブロックを決定し、
前記スーパーブロックに関連した有効性カウンタをデクリメントする、
ように動作し、前記有効性カウンタは前記揮発メモリに記憶される、請求項１６又は１７に記載のメモリインターフェイス。
【請求項１９】
前記ツリーが前記ＬＢＡに対応する論理的−物理的マッピングを含むとの決定に応答して、前記コントロール回路は、
前記ツリーを使用して前記ＬＢＡに関連したＮＶＭのスーパーブロックを決定し、
前記スーパーブロックに関連した有効性カウンタをデクリメントする、
ように動作し、前記有効性カウンタは前記揮発メモリに記憶される、請求項１６又は１７に記載のメモリインターフェイス。
【請求項２０】
不揮発性メモリ（ＮＶＭ）を備えたシステムの論理的ブロックアドレス（ＬＢＡ）をアンマップする装置であって、
揮発性メモリに記憶されたビットマップに複数のＬＢＡのマッピング状態を記憶する手段と、
第１のＬＢＡをアンマップする要求をファイルシステムから受信する手段と、
前記第１のＬＢＡのマッピング状態を、前記ビットマップを更新するだけでアンマップへと変更する手段と、
前記第１のＬＢＡに対応するスーパーブロックのための有効性カウンタを減少する手段と、
を備えた装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＬＢＡビットマップの使用に関する。
【背景技術】
【０００２】
ＮＡＮＤフラッシュメモリ及び他の形式の不揮発性メモリ（ＮＶＭ）は、一般的に、大量記憶に使用される。例えば、ポータブルメディアプレーヤのような消費者向け電子装置は、しばしば、音楽、ビデオ及び他のメディアを記憶するためにフラッシュメモリを備えている。
【０００３】
ＮＶＭを有するシステムは、ＮＶＭに記憶されたインデックスページを含み、これは、論理的ブロックアドレス（ＬＢＡ）のマッピング状態を示すものである。例えば、ＬＢＡのマッピング状態が「マップ」である場合には、これは、ＬＢＡが、現在、ＮＶＭに記憶されたデータに関連していることを示す。或いは又、ＬＢＡのマッピング状態が「アンマップ」である場合には、これは、その前にＬＢＡにマップされたデータが消去されたか、又はＬＢＡがいずれのデータにもマップされていないことを示す。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ＬＢＡのマッピング状態はインデックスページに記憶されるので、システムは、ＬＢＡがマップされるか又はアンマップされるたびにインデックスページを更新して、ＮＶＭにおいてプログラミングオペレーションを遂行する必要がある。付加的なプログラミングオペレーションのたびに、システムは、結局、ＮＶＭにおいてガーベージコレクションを遂行して、スペースを解放することが必要になる。これは、ひいては、システム性能を低下させる。
【課題を解決するための手段】
【０００５】
不揮発性メモリ（ＮＶＭ）を有するシステムの論理的ブロックアドレス（ＬＢＡ）ビットマップ使用のためのシステム及び方法が開示される。システムの揮発性メモリに記憶できるビットマップは、１つ以上の論理的アドレス（例えば、ＬＢＡ）のマッピング状態を記憶することができる。ビットマップを使用して、システムは、ＮＶＭにアクセスする必要なく、ＬＢＡのマッピング状態を決定することができる。更に、システムは、最小限のＮＶＭアクセスでＬＢＡのマッピング状態を更新することができる。ＮＶＭアクセスの回数を減少することにより、システムは、ガーベージコレクションプロセスをトリガーすることを回避でき、全体的なシステム性能を改善することができる。
【０００６】
本発明の前記及び他の態様及び効果は、全体にわたって同じ参照文字で同じ部分を示した添付図面を参照して以下の詳細な説明を考慮したときに明らかとなるであろう。
【図面の簡単な説明】
【０００７】
【図１】本発明の種々の実施形態により構成された電子装置のブロック図である。
【図２】本発明の種々の実施形態によるメモリマッピングアーキテクチャーを例示するブロック図である。
【図３】本発明の種々の実施形態により構成された電子装置の別のブロック図である。
【図４Ａ】本発明の種々の実施形態によるビットマップを例示する。
【図４Ｂ】本発明の種々の実施形態によるビットマップを例示する。
【図４Ｃ】本発明の種々の実施形態によるビットマップを例示する。
【図５】本発明の種々の実施形態によりビットマップを使用して非マップ要求を取り扱うためのプロセスを例示するフローチャートである。
【図６】本発明の種々の実施形態によりビットマップを使用して読み取り要求を取り扱うためのプロセスを例示するフローチャートである。
【図７】本発明の種々の実施形態によりツリーを更新するためのプロセスを例示するフローチャートである。
【図８】本発明の種々の実施形態により有効性カウンタを更新するためのプロセスを例示するフローチャートである。
【図９】本発明の種々の実施形態により高速ガーベージコレクションを行うためのプロセスを例示するフローチャートである。
【発明を実施するための形態】
【０００８】
不揮発性メモリ（ＮＶＭ）を有するシステムの論理的ブロックアドレス（ＬＢＡ）ビットマップ使用のためのシステム及び方法が提供される。システムの揮発性メモリに記憶できるビットマップは、１つ以上の論理的アドレス（例えば、ＬＢＡ）のマッピング状態を記憶することができる。ビットマップの各エントリは、１つ以上のＬＢＡに対応する。
【０００９】
ビットマップを使用して、システムのＮＶＭインターフェイスは、ＮＶＭにアクセスする必要なく、ＬＢＡのマッピング状態を決定することができる。更に、ＮＶＭインターフェイスは、最小限のＮＶＭアクセスでＬＢＡのマッピング状態を更新することができる。例えば、特定のＬＢＡをアンマップするための要求をファイルシステムから受け取るのに応答して、ＮＶＭインターフェイスは、ビットマップの対応エントリのマッピング状態を「マップ」から「アンマップ」へ変更することができる。ＮＶＭアクセスの回数を減少することにより、システムは、ガーベージコレクションプロセスをトリガーすることを回避でき、全体的なシステム性能を改善することができる。
【００１０】
ビットマップを更新することによりＬＢＡのマッピング状態を変更した後、ＮＶＭインターフェイスは、揮発性メモリに記憶されたツリーを調べて、これも揮発性メモリに記憶された少なくとも１つの有効性カウンタを更新することができる。しかしながら、ＬＢＡとＮＶＭの物理的アドレスとの間のマッピングを含むことのできるツリーは、必ずしも、ＬＢＡのアンマッピングを反映するように更新される必要はない。むしろ、ＮＶＭインターフェイスは、ツリーメモリの使用が好都合にも減少される場合だけツリーの更新を行うことを決定できる。
【００１１】
ＮＶＭインターフェイスが、ツリーを調べることで少なくとも１つの有効性カウンタを更新できない状況では、ＮＶＭインターフェイスは、ＬＢＡに関連したインデックスページをＮＶＭからロードする必要がある。ＮＶＭインターフェイスは、インデックスページを揮発性メモリに読み込む必要はあるが、インデックスページを更新してＮＶＭに再プログラムする必要はない。その正味の結果として、遂行される必要のあるインデックスページオペレーションの合計数を減少し、ガーベージコレクションを回避することができる。
【００１２】
ある実施形態では、ビットマップは、ガーベージコレクションプロセスを改善することができる。特に、ビットマップを使用して、ＮＶＭインターフェイスは、ＮＶＭに記憶されたユーザデータに対してガーベージコレクションを遂行しながら行う必要のあるインデックスページアクセスの回数を減少することができる。
【００１３】
図１は、電子装置１００のブロック図である。ある実施形態において、電子装置１００は、ポータブルメディアプレーヤ、セルラー電話、ポケットサイズパーソナルコンピュータ、パーソナルデジタルアシスタント（ＰＤＡ）、デスクトップコンピュータ、ラップトップコンピュータ、及び他の適当な形式の電子装置であるか、又はそれらを含む。
【００１４】
電子装置１００は、システムオンチップ（ＳｏＣ）１１０及び不揮発性メモリ（ＮＶＭ）１２０を備えている。不揮発性メモリ１２０は、フローティングゲート又は電荷トラップ技術に基づくＮＡＮＤフラッシュメモリ、ＮＯＲフラッシュメモリ、消去可能なプログラマブルリードオンリメモリ（ＥＰＲＯＭ）、電気的に消去可能なプログラマブルリードオンリメモリ（ＥＥＰＲＯＭ）、強誘電体ＲＡＭ（ＦＲＡＭ）、磁気抵抗性ＲＡＭ（ＭＲＡＭ）、又はその組み合わせを含む。
【００１５】
ＮＶＭ１２０は、消去可能な最小単位である「ブロック」へと編成され、そして更に、プログラム又は読み取り可能な最小単位である「ページ」へと編成される。ある実施形態では、ＮＶＭ１２０は、複数の集積回路を含み、各集積回路は複数のブロックを有する。対応する集積回路からのメモリ位置（例えば、ブロック又はブロックのページ）で「スーパーブロック」が形成される。ＮＶＭ１２０の各メモリ位置（例えば、ページ又はブロック）は、物理的アドレス（例えば、物理的ページアドレス又は物理的ブロックアドレス）を使用して参照される。
【００１６】
図２を参照すれば、論理的アドレスを物理的アドレスにマッピングするための例示的なメモリマッピングアーキテクチャー２００が示されている。このアーキテクチャー２００は、揮発性メモリ（破線の左側に示す）及び不揮発性メモリ（破線の右側に示す）に分割される。即ち、ルックアップテーブル２０２、インデックステーブルキャッシュ２０４、ツリー２１０及びビットマップ２１２は、揮発性メモリ（例えば、図１のメモリ１１４）に記憶され、一方、インデックステーブル２０６及びデータページ２０８は、不揮発性メモリ（例えば、図１のＮＶＭ１２０）に記憶される。
【００１７】
ＮＶＭの１つ以上のページは、ＳｏＣ（例えば、図１のＳｏＣ１１０）又は装置（例えば、図１の装置１００）のコンポーネントの一般的なオペレーションに関連したデータを記憶するのに使用できるデータページ２０８である。ある実施形態では、ブロックテーブル・オブ・コンテンツ（ＴＯＣ）を各データブロックに関連付けることができる。例えば、図２に示す例では、ブロックＴＯＣ１は、データブロック１に関連し、ブロックＴＯＣＮは、データブロックＮに関連し、等々である。各ブロックＴＯＣは、それに対応するデータブロックに記憶され、そしてデータブロックのデータページをそれに対応する論理的アドレスへマップする情報を含むことができる。
【００１８】
更に、ＮＶＭの１つ以上のページを使用して、インデックステーブル２０６を記憶することができる。論理的セクタが物理的ページに直接マップされる実施形態では、論理的−物理的マッピングをインデックステーブル２０６に記憶することができる。ここに使用する「論理的−物理的マッピング」とは、データページの１つ以上の論理的アドレス（例えば、論理的セクタ）と物理的アドレス（例えば、物理的ページアドレス又はバーチャルブロックアドレス）との間のマッピングである。例えば、インデックステーブル２０６は、ＮＶＭのデータページ２０８の物理的アドレスを保持することができる。
【００１９】
あるケースでは、インデックステーブル２０６は、複数のインデックスページ１−Ｎを含み、各インデックスページは、データページ２０８の論理的アドレスを１つ以上の物理的アドレスへマップする（例えば、１つ以上の論理的−物理的マッピングを記憶する）ことができる。例えば、図２に示すように、インデックステーブル２０６のインデックスページ１は、論理的アドレスをデータブロック１及びデータブロックＮの１つ以上のデータページへマップすることができる。
【００２０】
図１へ戻ると、システムオンチップ１１０は、ＳｏＣコントロール回路１１２、メモリ１１４、及びＮＶＭインターフェイス１１８を備えている。ＳｏＣコントロール回路１１２は、ＳｏＣ１１０の一般的なオペレーション及びファンクション、並びにＳｏＣ１１０又は装置１００の他のコンポーネントをコントロールすることができる。例えば、アプリケーション又はオペレーティングシステムのユーザ入力及び／又はインストラクションに応答して、ＳｏＣコントロール回路１１２は、ＮＶＭ１２０からデータを得るか又はそこにデータを記憶するためにＮＶＭインターフェイス１１８へ読み取り又は書き込み要求を発行することができる。明瞭化のために、ＳｏＣコントロール回路１１２が記憶又は検索のために要求するデータは、ユーザ又はユーザアプリケーションに直接的に関連していないが、「ユーザデータ」と称される。むしろ、ユーザデータは、（例えば、アプリケーション又はオペレーティングシステムを経て）ＳｏＣコントロール回路１１２により発生され又は得られたデジタル情報の適当なシーケンスである。
【００２１】
ＳｏＣコントロール回路１１２は、ハードウェア、ソフトウェア、及びファームウェアの組み合わせ、並びに電子装置１００のファンクションを駆動するように動作するコンポーネント、回路又はロジックを含む。例えば、ＳｏＣコントロール回路１１２は、ＮＶＭ１２０又はメモリ１１４に記憶されるソフトウェア／ファームウェアのコントロールの下で動作する１つ以上のプロセッサを含むことができる。
【００２２】
メモリ１１４は、適当な形式の揮発性メモリ、例えば、ランダムアクセスメモリ（ＲＡＭ）（例えば、スタティックＲＡＭ（ＳＲＡＭ）、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、同期ダイナミックランダムアクセスメモリ（ＳＤＲＡＭ）、倍データレート（ＤＤＲ）ＲＡＭ）；キャッシュメモリ；リードオンリメモリ（ＲＯＭ）；又はその組み合わせを含む。メモリ１１４は、不揮発性メモリ１２０へプログラミングし又はそこから読み取りするためにユーザデータを一時的に記憶できるデータソースを含む。ある実施形態では、メモリ１１４は、ＳｏＣコントロール回路１１２の一部分として実施されるプロセッサのためのメインメモリとして働く。
【００２３】
ある実施形態において、メモリ１１４は、関連するオペレーションを遂行するためにＮＶＭインターフェイス１１８により使用される１つ以上のデータ構造体を記憶することができる。例えば、メモリ１１４は、ビットマップを含むことができる。これは、図２にも示されており、揮発性メモリは、ビットマップ２１２を含む。
【００２４】
ビットマップは、１つ以上の論理的アドレス（例えば、ＬＢＡ）のマッピング状態（例えば、「マップ(Mapped)」又は「アンマップ(Unmapped)」）を記憶することができる。例えば、ＬＢＡのマッピング状態が「マップ」である場合には、ＮＶＭインターフェイス１１８は、ＬＢＡが、現在、ＮＶＭ１２０に記憶されたユーザデータに関連していると決定することができる。或いは又、ＬＢＡのマッピング状態が「アンマップ」の場合には、ＮＶＭインターフェイス１１８は、ＬＢＡがそれ以前にユーザデータにマップされた（が、ユーザデータがそれ以来削除されている）か、又はＬＢＡがユーザデータに決してマップされていないと決定することができる。
【００２５】
ビットマップは、適当な時間にポピュレートすることができる。例えば、あるシステムでは、ファイルシステムは、システムブートアップ中にどのＬＢＡがアンマップであるかに関する情報を与えることができる。例えば、ファイルシステムがマウントされると、ＮＶＭインターフェイス１１８は、ＬＢＡのマッピング状態に関連した情報をファイルシステムから受け取ることができる。情報を受け取った後に、ＮＶＭインターフェイス１１８は、その情報を使用してビットマップをポピュレートすることができる。マッピング状態は、ファイルシステムから自動的に得られるので、全体的なシステムマウント時間を減少することができる。しかしながら、ファイルシステムが、ブートアップ中にどのＬＢＡがアンマップであるかに関する情報を与えない場合には、ＮＶＭインターフェイス１１８は、ＮＶＭ１２０をスキャンすることによりマッピング状態を得ることができる。システムオペレーション中に、ビットマップは、ＮＶＭインターフェイス１１８により動的に維持されそして使用される。
【００２６】
ビットマップは、例えば、２ＭＢのような適当なサイズをもつことができる。ビットマップに割り当てられるメモリの量は、１つ以上のファクタに依存する。例えば、ビットマップが小さいほど、他の情報（例えば、ツリー）を記憶するためにメモリ１１４においてより広いスペースを利用することができる。対照的に、ビットマップが大きいほど、ビットマップの各エントリを単一のＬＢＡに対応させることができ、これは、ＮＶＭインターフェイス１１８に、各ＬＢＡのマッピング状態に関する決定的な情報を与えることができる。いずれにせよ、ビットマップは、マッピング状態に加えて物理的及び／又は論理的アドレスを記憶するのに必要な異なるデータ構造（例えば、テーブル）に比して小さなサイズをもつことができる。図４Ａ−４Ｃを参照して種々の形式のビットマップについて詳細に説明する。
【００２７】
別の例として、メモリ１１４は、複数のツリーエントリを含むツリーを含むことができる。例えば、図２に示すように、ツリー２１０は、論理的アドレス（例えば、ＬＢＡ）とＮＶＭ（例えば、図１のＮＶＭ１２０）の対応物理的アドレスとの間のマッピングを与えることができる。ツリー２１０は、例えば、ｂツリー又はｂ＊ツリーのようなツリーの特定のエントリのための検索時間を改善するツリー構造を有する。あるケースでは、ツリー２１０には、揮発性メモリにおいて所定量のツリーメモリが割り当てられる。
【００２８】
更に別の例として、メモリ１１４は、ルックアップテーブル及び／又はインデックステーブルキャッシュを含む。例えば、図２に示すように、ルックアップテーブル２０２は、インデックステーブル２０６の位置（例えば、物理的アドレス）を保持する。特に、ルックアップテーブル２０２は、インデックステーブル２０６の一部分を形成するインデックスページ１−Ｎの論理的−物理的マッピングを保持する。更に、ルックアップテーブル２０２は、インデックステーブルキャッシュ２０４のメモリ位置も記憶する。
【００２９】
インデックステーブルキャッシュ２０４は、より速い読み出しを与えるため、最近書き込まれ又はアクセスされた論理的アドレス（例えば、論理的セクタ）の物理的アドレスを保持することができる。即ち、キャッシュ２０４は、現在プログラムされているか又は最近プログラムされたデータページ２０８に対する論理的−物理的マッピングを保持する。周期的ベースで、インデックステーブルキャッシュ２０４に記憶された情報をフラッシュアウトして、ＮＶＭのページ１−Ｎをインデックスすることができる。
【００３０】
図１に戻ると、ＮＶＭインターフェイス１１８は、ＳｏＣコントロール回路１１２とＮＶＭ１２０との間のインターフェイス又はドライバとして働くように構成されたハードウェア、ソフトウェア及び／又はファームウェアの適当な組み合わせを含む。ＮＶＭインターフェイス１１８に含まれたソフトウェアモジュールの場合に、対応するプログラムコードは、ＮＶＭ１２０又はメモリ１１４に記憶される。
【００３１】
ＮＶＭインターフェイス１１８は、ＳｏＣコントロール回路１１２がＮＶＭ１２０にアクセスしそしてＮＶＭ１２０のメモリ位置（例えば、ページ、ブロック、スーパーブロック、集積回路）及びそこに記憶されたデータ（例えば、ユーザデータ）を管理できるようにする種々のファンクションを遂行することができる。例えば、ＮＶＭインターフェイス１１８は、ＳｏＣコントロール回路１１２からの読み取り又は書き込み要求を解釈し、ウェアレベリングを遂行し、そしてＮＶＭ１２０のバスコントロールに適合する読み取り及びプログラムインストラクションを発生することができる。
【００３２】
ＮＶＭインターフェイス１１８及びＳｏＣコントロール回路１１２は、個別モジュールとして示されているが、これは、本発明の実施形態の説明を簡単にするために過ぎない。これらのモジュールは、ハードウェアコンポーネント、ソフトウェアコンポーネント又はその両方を共有できることを理解されたい。例えば、ＳｏＣコントロール回路１１２は、ＮＶＭインターフェイス１１８のためのソフトウェアベースのメモリドライバを実行することができる。
【００３３】
ある実施形態において、電子装置１００は、ＮＶＭ１２０、及びＮＶＭインターフェイス１１８の全部分又はある部分を含むフラッシュメモリドライブ又はＳＤカードのようなターゲット装置を含む。これらの実施形態において、ＳｏＣ１１０又はＳｏＣコントロール回路１１２は、ターゲット装置のためのホストコントローラとして働く。例えば、ホストコントローラとして、ＳｏＣ１１０は、読み取り及び書き込み要求をターゲット装置へ発行する。
【００３４】
図３は、電子装置３００のブロック図で、種々の実施形態による電子装置１００（図１）のファームウェア、ソフトウェア、及び／又はハードウェアコンポーネントの幾つかを更に詳細に示している。電子装置３００は、図１を参照して上述した特徴及びファンクションのいずれを有してもよく、及びその逆のことも言える。図示されたように、破線は、層の境界を定めるものである。どのコンポーネントが境界線内に入るかの説明は、単なる例示に過ぎず、１つ以上のコンポーネントを異なる層に関連させてもよいことを理解されたい。
【００３５】
電子装置３００は、ファイルシステム３１０、ＮＶＭドライバ３１２、ＮＶＭバスコントローラ３１６、及びＮＶＭ３２０を備えている。ある実施形態では、ファイルシステム３１０及びＮＶＭドライバ３１２は、ソフトウェア又はファームウェアモジュールであり、そしてＮＶＭバスコントローラ３１６及びＮＶＭ３２０は、ハードウェアモジュールである。従って、これらの実施形態では、ＮＶＭドライバ３１２は、ＮＶＭインターフェイス３１８のソフトウェア又はファームウェア態様を表わし、そしてＮＶＭバスコントローラ３１６は、ＮＶＭインターフェイス３１８のハードウェア態様を表わす。
【００３６】
ファイルシステム３１０は、ファイルアロケーションテーブル（ＦＡＴ）ファイルシステム又はハイアラーキーファイルシステムプラス（ＨＦＳ＋）のような適当な形式のファイルシステムを含み、そして電子装置３００のオペレーティングシステムの一部分（例えば、図１のＳｏＣコントロール回路１１２の一部分）でよい。ある実施形態では、ファイルシステム３１０は、ページの論理的−物理的マッピングを与えるフラッシュファイルシステムを含む。これらの実施形態では、ファイルシステム３１０は、以下に述べるＮＶＭドライバ３１２のファンクションの幾つか又は全部を遂行し、それ故、ファイルシステム３１０及びＮＶＭドライバ３１２は、個別のモジュールであってもなくてもよい。
【００３７】
ファイルシステム３１０は、アプリケーション及びオペレーティングシステムのためのファイル及びフォルダ構造を管理する。ファイルシステム３１０は、電子装置３００で実行されるアプリケーション又はオペレーティングシステムのコントロールの下で動作し、そして情報をＮＶＭ３２０から読み取るか又はそこに記憶することをアプリケーション又はオペレーティングシステムが要求するときに書き込み又は読み取り要求をＮＶＭ装置３１２に与える。各読み取り又は書き込み要求と共に、ファイルシステム３１０は、ユーザデータを読み取り又は書き込むべき場所を指示するための論理的アドレス、例えば、ページオフセットを伴う論理的ページアドレス又は論理的ブロックアドレスを与える。
【００３８】
ファイルシステム３１０は、ＮＶＭ３２０に直接適合しない読み取り及び書き込み要求をＮＶＭドライバ３１２に与える。例えば、論理的アドレスは、ハードドライブベースシステムの典型である慣習又はプロトコルを使用する。ハードドライブベースシステムは、フラッシュメモリとは異なり、ブロック消去を最初に遂行せずにメモリ位置にオーバーライトすることができる。更に、ハードドライブは、装置の寿命を延ばすためにウェアレベリングを必要としない。それ故、ＮＶＭインターフェイス３１８は、ファイルシステム要求を取り扱うためにメモリ特有、ベンダー特有又はその両方であるファンクションを遂行すると共に、ＮＶＭ３２０に適した仕方で他の管理ファンクションを遂行することができる。
【００３９】
ＮＶＭドライバ３１２は、変換層３１４を含む。ある実施形態では、変換層３１４は、フラッシュ変換層（ＦＴＬ）であるか又はそれを含む。書き込み要求の際に、変換層３１４は、与えられた論理的アドレスを、ＮＶＭ３２０上の消去された空き物理的位置へマッピングする。読み取り要求の際に、変換層３１４は、与えられた論理的アドレスを使用して、要求されたデータが記憶された物理的アドレスを決定する。各ＮＶＭは、ＮＶＭのサイズ又はベンダーに基づいて異なるレイアウトを有するので、このマッピングオペレーションは、メモリ及び／又はベンダー特有のものである。
【００４０】
論理的−物理的アドレスマッピングに加えて、変換層３１４は、フラッシュ変換層について典型的である他の適当なファンクション、例えば、ガーベージコレクション（ＧＣ）及びウェアレベリングを遂行する。
【００４１】
ある実施形態では、ＮＶＭドライバ３１２は、ＮＶＭバスコントローラ３１６とインターフェイスして、ＮＶＭアクセス要求（例えば、プログラム、読み取り及び消去要求）を完了する。バスコントローラ３１６は、ＮＶＭ３２０へのハードウェアインターフェイスとして働き、そしてＮＶＭ３２０のバスプロトコル、データレート、及び他の仕様を使用して、ＮＶＭ３２０と通信する。
【００４２】
ＮＶＭインターフェイス３１８は、ここで「メタデータ」とも称されるメモリ管理データに基づいてＮＶＭ３２０を管理する。メタデータは、ＮＶＭドライバ３１２により発生されるか、又はＮＶＭドライバ３１２のコントロールの下で動作するモジュールにより発生される。例えば、メタデータは、論理的アドレスと物理的アドレスとの間のマッピングを管理するのに使用される情報、不良ブロックの管理、ウェアレベリング、データエラーを検出又は修正するのに使用されるＥＣＣデータ、或いはその組み合わせを含む。メタデータは、ファイルシステム３１０によって与えられるデータを、論理的アドレスのようなユーザデータと共に含む。従って、一般的に、「メタデータ」とは、ユーザデータに関する又は関連した情報を指すか、或いは不揮発性メモリのオペレーション及びメモリ位置を管理するために一般的に使用されるものである。
【００４３】
ＮＶＭインターフェイス３１８は、ＮＶＭ３２０にメタデータを記憶するように構成される。ある実施形態では、ＮＶＭインターフェイス３１８は、ユーザデータに関連したメタデータを、ユーザデータが記憶された同じメモリ位置（例えば、ページ）に記憶する。例えば、ＮＶＭインターフェイス３１８は、ユーザデータ、それに関連した論理的アドレス、及びユーザデータのためのＥＣＣデータを、ＮＶＭ３２０の１つ以上のメモリ位置に記憶する。又、ＮＶＭインターフェイス３１８は、ユーザデータに関する他の形式のメタデータも、同じメモリ位置に記憶する。
【００４４】
ＮＶＭインターフェイス３１８は、ＮＶＭ３２０のパワーアップ時又はＮＶＭ３２０のオペレーション中に、その位置にどんなデータがあるか電子装置３００が決定できるように論理的アドレスを記憶する。特に、ファイルシステム３１０は、ユーザデータを、その物理的アドレスではなく、その論理的アドレスに基づいて参照するので、ＮＶＭインターフェイス３１８は、ユーザデータ及び論理的アドレスを一緒に記憶してその関連性を維持することができる。このようにして、論理的−物理的マッピングをＮＶＭ３２０に維持する個別のテーブルが古くなっても、ＮＶＭインターフェイス３１８は、例えば、電子装置３００のパワーアップ時又は再ブート時に適切なマッピングを依然として決定することができる。
【００４５】
上述したように、揮発性メモリに記憶できるビットマップは、１つ以上のＬＢＡのマッピング状態を記憶することができる。更に、ビットマップの各エントリは、１つ以上のＬＢＡに対応する。例えば、図４Ａ−４Ｃを参照すれば、種々のビットマップが例示されている。当業者であれば、ビットマップは、適当な数のエントリを含むことが明らかであろう。しかしながら、簡単化のために、図４Ａ−４Ｃの各ビットマップは、８つのエントリしか含まないように示されている。
【００４６】
先ず、図４Ａを参照すれば、ビットマップ４００は、エントリ４００Ａ−Ｈを含む。ビットマップ４００の各エントリは、単一のＬＢＡに対応する。従って、例えば、エントリ４００Ａ−Ｈは、各々、ＬＢＡ０−７に対応する。更に、各エントリは、１ビットに対応する。即ち、ビットマップ４００の各エントリは、バイナリ値（例えば、０又は１）を記憶し、各バイナリ値は、「アンマップ」又は「マップ」のマッピング状態に対応する。データがＬＢＡにプログラムされそして対応するビットマップエントリが「アンマップ」のマッピング状態を有するとき、ビットマップエントリは、「マップ」のマッピング状態を反映するように更新することができる。しかしながら、対応するビットマップエントリが既に「マップ」のマッピング状態を有する場合には、ＬＢＡが既に記憶されているブロックの有効性カウンタを減少することができる。
【００４７】
ビットマップ４００の各エントリは、単一のＬＢＡに対応するので、ビットマップ４００は、ＮＶＭインターフェイス（例えば、図１のＮＶＭインターフェイス１１８又は図３のＮＶＭ３１８）に、特定のＬＢＡがマップであるかアンマップであるかに関する決定的な情報を与えることができる。別の構成では、ＬＢＡへのエントリの粒度を減少して、ビットマップの各エントリが複数のＬＢＡ（例えば、８、１６又は３２個のＬＢＡ）に対応するようにすることができる。このような構成は、システムの各ＬＢＡに対する決定的なマッピング状態を与えないが、これらのビットマップは、小さなものであり（例えば、２ＭＢではなく２５６ｋＢ）、メモリ（例えば、図１のメモリ１１４）の付加的なスペースを節約する。付加的なメモリスペースは、例えば、大きなツリー（例えば、図２のツリー２１０）を記憶する、等の他の目的で使用することができる。
【００４８】
他の実施形態では、ビットマップの各エントリが複数のＬＢＡに対応する。例えば、図４Ｂを参照すれば、ビットマップ４０２は、エントリ４０２Ａ−Ｈを含み、各エントリには８個のＬＢＡが関連される。更に、各エントリは、依然、１ビットに対応する。即ち、各エントリは、バイナリ値を記憶することができ、各バイナリ値は、「全マップ／全アンマップ」又は「未知」のマッピング状態に対応する。例えば、図４Ｂに示すように、エントリが「イエス」表示を有する場合には、そのエントリに対応する全てのＬＢＡは、ビットマップ４０２が構成される仕方に基づき、全マップ又は全アンマップのいずれかであると考えられる。対照的に、エントリが「Ｍｉｘ」表示を有する場合には、そのエントリに対応するＬＢＡのマッピング状態は、「未知」であると考えられる。従って、そのエントリに対応する１つ以上のＬＢＡをアンマップする一方、残りのＬＢＡをマップすることができる。
【００４９】
図４Ｃを参照すれば、ビットマップ４０４は、エントリ４０４Ａ−Ｈを含み、各エントリは、８個のＬＢＡに対応する。しかしながら、このケースでは、各エントリは、複数のビット（例えば、２ビット）を記憶することができる。従って、ビットマップ４０４の各エントリは、３つの値の１つに対応し、各値は、適当なマッピング状態（例えば、「マップ」、「アンマップ」又は「Ｍｉｘ」）に対応する。例えば、図４Ｃに示すように、エントリが「マップ」表示を有する場合には、そのエントリに対応する全ＬＢＡをマップすることができる。同様に、エントリが「アンマップ」表示を有する場合には、そのエントリに対応する全ＬＢＡをアンマップすることができる。対照的に、エントリが「Ｍｉｘ」表示を有する場合には、そのエントリに対応する１つ以上のＬＢＡをアンマップする一方、残りのＬＢＡをマップすることができる。
【００５０】
ビットマップ４０２及び４０４について、エントリのマッピング状態が未知の状態である（例えば、ＮＶＭインターフェイスがエントリに対し「未知」又は「Ｍｉｘ」値に遭遇する）ことをＮＶＭインターフェイスが決定した場合には、ＮＶＭインターフェイスは、そのエントリに関連した各ＬＢＡのマッピング状態を個別に決定し及び／又は更新することが必要になる。例えば、ＮＶＭインターフェイスは、例えば、ツリー（例えば、図２のツリー２１０）及び／又は１つ以上のインデックスページ（例えば、図２のインデックスページ１−Ｎ）のようなシステムの１つ以上のデータ構造を調べそして更新することができる。その結果、ビットマップは、「未知」又は「Ｍｉｘ」値の数がビットマップにおいて増加するのでＬＢＡのマッピング状態を決定する上であまり有用でなくなる。
【００５１】
更に、「マップ」エントリに関連したＬＢＡがここでアンマップされる場合には、そのエントリは、「未知」又は「Ｍｉｘ」のマッピング状態をもつよう更新する必要がある。その結果、ＬＢＡのマッピング状態を監視し続けるために、ＮＶＭインターフェイスは、ツリー及び／又は１つ以上のインデックスページを更新して、ＬＢＡの変更されたマッピング状態を反映することが必要になる。
【００５２】
従って、ビットマップの粒度は、例えば、現在のメモリ利用度、所与の粒度に対する各ＬＢＡのマッピング状態を決定的に決定するのに必要なデューティサイクル、システム使用モデル、及び／又はその組み合わせ、等の１つ以上のファクタに基づいて決定される。システム使用モデルは、書き込まれ及び／又は削除されるファイルのサイズを含む。例えば、システムが大きなファイルを順次に書き込み及び削除する場合には、ＬＢＡへのエントリのより大きな粒度をビットマップに対して選択することができる。対照的に、システムが小さなファイルを書き込み及び削除する場合には、ＬＢＡへのエントリのより微細な粒度をビットマップに対して選択して、各ＬＢＡの充分な情報を与えることができる。
【００５３】
ある実施形態では、ＮＶＭインターフェイスは、システムが動作している間にビットマップの粒度を動的に調整する（例えば、所与のレベルにおける未知の状態の頻度に基づき各ビットマップエントリの範囲を増加又は減少する）。例えば、ＮＶＭインターフェイスは、各エントリが１つのＬＢＡに対応するようにビットマップを最初に初期化する。次いで、システムが動作を続けるときに、ＮＶＭインターフェイスは、例えば、未知の状態をもつエントリの数が所定のスレッシュホールド未満である（例えば、未知の状態をもつビットマップエントリの５０％未満である）場合には、各エントリに対応するＬＢＡの数を増加することができる。他の実施形態では、ＮＶＭインターフェイスは、ビットマップの各エントリがＬＢＡの静的な所定の数に対応する（例えば、各エントリが１つのＬＢＡに対応するか、又は各エントリが３２個のＬＢＡに対応する）ようにビットマップを初期化することができる。
【００５４】
システムは、ビットマップを使用して、ＬＢＡのマッピング状態を種々のシナリオで監視することができる。従来、システムがＬＢＡのマッピング状態を決定するために、システムは、特に、システムがツリーを維持しない場合、又はＬＢＡのマッピング状態がツリーによって部分的に捕えられるだけである場合に、ＮＶＭ（例えば、図１のＮＶＭ１２０又は図３のＮＶＭ３２０）を調べることが必要である。例えば、１つ以上のＬＢＡをアンマップするために、システムは、ＮＶＭに記憶された１つ以上のインデックスページ（例えば、図２のインデックスページ１−Ｎ）を、メモリ（例えば、図１のメモリ１１４）に記憶されたインデックステーブルキャッシュ（例えば、図２のインデックステーブルキャッシュ２０４）へ最初に読み込むことが必要である。次いで、インデックスページは、１つ以上のＬＢＡのアンマッピングを反映するようにインデックステーブルキャッシュにおいて更新される（例えば、関連する物理的アドレスをデフォールト値と置き換えることにより）。その後、更新されたインデックスページは、ＮＶＭへプログラムして戻される。しかしながら、これらの付加的なプログラミングオペレーションは、ＮＶＭのガーベージコレクションを早目にトリガーし、システム性能に否定的な影響を及ぼす。
【００５５】
ＬＢＡのマッピング状態がツリーにより完全に捕えられる他のシステムでは、システムは、ＬＢＡをアンマップするためにツリーを更新する必要がある。その後、ツリーメモリ使用が所定のスレッシュホールドを越えると決定されたときに、ツリーの１つ以上の部分（例えば、エントリ）を平坦化することができる。しかしながら、平坦化オペレーションは、その平坦化されたエントリに対応するデータをＮＶＭにおいて再プログラムする必要があるので、ＮＶＭにおいて付加的なオペレーションも伴う。これらオペレーションは、その後、ガーベージコレクションをトリガーすることがある。
【００５６】
別の例として、従来のシステムにおいてＬＢＡを読み取るためには、ＮＶＭに記憶されたインデックスページを調べる必要がある（例えば、図２のインデックステーブルキャッシュ２０４のようなインデックステーブルキャッシュにインデックスページが記憶されていない場合）。従って、システムは、ＬＢＡがマップであるかアンマップであるか決定できる前に、全インデックスページをメモリ（例えば、図１のメモリ１１４）へ読み込むことが必要である。
【００５７】
従って、メモリ（例えば、図１のメモリ１１４）に記憶されたビットマップ（例えば、図４Ａ−４Ｃのビットマップ、各々４００、４０２又は４０４）に依存することにより、ＮＶＭインターフェイス（例えば、図１のＮＶＭインターフェイス１１８又は図３のＮＶＭインターフェイス３１８）は、ＮＶＭにアクセスする必要なく、ＬＢＡのマッピング状態を決定することができる。更に、ＮＶＭインターフェイスは、ＬＢＡのマッピング状態を最小のＮＶＭアクセスで更新することができる。ＮＶＭアクセスの回数を減少することにより、システムは、ガーベージコレクションプロセスをトリガーすることを回避し、システムの全体的な性能を改善することができる。例えば、図５及び６は、本発明の種々の実施形態によるプロセスを例示するフローチャートである。
【００５８】
先ず、図５を参照すると、ビットマップを使用してアンマップ要求を取り扱うためのプロセス５００が示されている。プロセス５００は、ステップ５０２で始まり、そしてステップ５０４において、ＮＶＭインターフェイスは、揮発性メモリ（例えば、図１のメモリ１１４）に記憶されたビットマップ（例えば、図４Ａ−４Ｃのビットマップ、各々、４００、４０２又は４０４）に複数のＬＢＡのマッピング状態を記憶することができる。例えば、上述したように、ＮＶＭインターフェイスは、システムブートアップ中に、又はＮＶＭ（例えば、図１のＮＶＭ１２０又は図３のＮＶＭ３２０）のスキャニングにより、ファイルシステム（例えば、図３のファイルシステム３１０）からマッピング状態を得ることができる。
【００５９】
ステップ５０６において、ＮＶＭインターフェイスは、ＬＢＡをアンマップするための要求をファイルシステムから受け取る。ステップ５０８へと続いて、ＮＶＭインターフェイスは、ＬＢＡのマッピング状態を、ビットマップを更新するだけでアンマップへと変更する。例えば、図４Ａを参照すると、ＮＶＭインターフェイスが、ＬＢＡ０をアンマップするための要求を受け取る場合に、ＮＶＭインターフェイスは、エントリ４００Ａのマッピング状態を「マップ」から「アンマップ」へ変更する。ビットマップを更新することによりＬＢＡのマッピング状態を変更した後に、ＮＶＭインターフェイスは、メモリ（例えば、図１のメモリ１１４）に記憶された少なくとも１つの有効性カウンタを更新する。少なくとも１つの有効性カウンタは、ＬＢＡに関連したスーパーブロックに対応する。マッピング状態を変更した後に、プロセス５００は、ステップ５１０で終了する。
【００６０】
図６を参照すれば、ビットマップを使用して読み取り要求を取り扱うためのプロセス６００が示されている。プロセス６００は、ステップ６０２で開始し、そしてステップ６０４において、ＮＶＭインターフェイス（例えば、図１のＮＶＭインターフェイス１１８又は図３のＮＶＭインターフェイス３１８）は、ＬＢＡを読み取るための読み取り要求をファイルシステム（例えば、図３のファイルシステム３１０）から受け取る。
【００６１】
次いで、ステップ６０６において、ＮＶＭインターフェイスは、ＬＢＡに関連したビットマップ（例えば、図４Ａ−４Ｃのビットマップ、各々、４００、４０２又は４０４）のエントリを調べる。ステップ６０８へと続いて、ＮＶＭインターフェイスは、ＬＢＡがアンマップされたことをエントリが指示するかどうか決定する。
【００６２】
ステップ６０８において、ＬＢＡがアンマップされたことをエントリが指示するとＮＶＭインターフェイスが決定する場合には、プロセス６００は、ステップ６１０へ進む。例えば、図４Ａを参照すれば、ＮＶＭインターフェイスが、ＬＢＡ２を読み取る要求を受け取る場合に、ＮＶＭインターフェイスは、ビットマップ４００のエントリ４００Ｃを調べることによりＬＢＡ２がアンマップされたと決定する。
【００６３】
ステップ６１０において、ＮＶＭインターフェイスは、ＬＢＡが関連ユーザデータをもたないことを指示する情報をファイルシステムへ送信する。従って、ＮＶＭインターフェイスは、ＮＶＭに記憶されたインデックスページを調べる必要なく、ＬＢＡのマッピング状態を直接決定することができる。プロセス６００は、ステップ６１２において終了となる。
【００６４】
ステップ６０８に戻ると、ＬＢＡがアンマップされないことをエントリが指示するとＮＶＭインターフェイスが決定する場合には、プロセス６００は、ステップ６１４へ進む。ステップ６１４において、ＮＶＭインターフェイスは、ＮＶＭ（例えば、図１のＮＶＭ１２０又は図３のＮＶＭ３２０）のインデックスページを調べて、ＬＢＡに関連したユーザデータの位置を求める。従って、従来のシステムとは対照的に、ＮＶＭインターフェイスは、ＬＢＡがマップされたことをビットマップエントリが指示する場合にインデックスページを調べるだけでよい。
【００６５】
ユーザデータの位置を求めた後に、ＮＶＭインターフェイスは、ステップ６１６において、ユーザデータをファイルシステムに送信する。次いで、プロセス６００は、ステップ６１２において終了となる。
【００６６】
ある実施形態において、ビットマップを更新することによりＬＢＡのマッピング状態を変更した後に、ＮＶＭインターフェイスは、ツリーを調べて、メモリ（例えば、図１のメモリ１１４）に記憶された有効性カウンタを更新することができる。有効性カウンタは、ＮＶＭのスーパーブロックごとに維持される。ある実施形態では、有効性カウンタは、メモリにテーブルとして記憶される。
【００６７】
ＮＶＭインターフェイスは、有効性カウンタを更新する際にツリーを調べることができるが、ツリーは、必ずしも、ＬＢＡのアンマッピングを反映するように更新される必要がない。これは、ファイルシステムにより使用されるＬＢＡのマッピング状態をビットマップが既に記憶しているからである。むしろ、ＮＶＭインターフェイスは、ツリーメモリの使用が好都合にも減少される場合だけツリー更新を遂行する。さもなければ、ＮＶＭインターフェイスは、ツリーを現在状態のままにする。
【００６８】
例えば、図７は、ツリー（例えば、図２のツリー２１０）を更新するためのプロセス７００を例示するフローチャートである。プロセス７００は、ステップ７０２で開始し、そしてステップ７０４において、ＮＶＭインターフェイス（例えば、図１のＮＶＭインターフェイス１１８又は図３のＮＶＭインターフェイス３１８）は、ＬＢＡをアンマップするための要求を受け取る。
【００６９】
ステップ７０６へ続いて、ＮＶＭインターフェイスは、ビットマップ（例えば、図４Ａ−４Ｃのビットマップ、各々、４００、４０２又は４０４）を調べて、ＬＢＡがアンマップされたかどうか決定する。ステップ７０８において、ＬＢＡがアンマップされるとＮＶＭインターフェイスが決定した場合には、プロセス７００は、ステップ７１０へ進む。
【００７０】
ある実施形態では、ステップ７１０において、ＮＶＭインターフェイスは、ＬＢＡが既にアンマップされたことを示す情報をファイルシステム（例えば、図３のファイルシステム３１０）へ送信する。従って、プロセス６００（図６）のステップ６１０のように、ＬＢＡがアンマップされたと決定するためにＮＶＭにアクセスする必要はない。次いで、プロセス７００は、ステップ７１２で終了となる。
【００７１】
ステップ７０８に戻ると、ＬＢＡがアンマップされないとＮＶＭインターフェイスが決定する場合には、プロセス７００は、ステップ７１４へ進む。ステップ７１４において、ＮＶＭインターフェイスは、ＬＢＡをアンマップする。
【００７２】
ステップ７１６へと続いて、ＮＶＭインターフェイスは、ツリーを調べることによって１つ以上の有効性カウンタを更新する。特に、ＮＶＭインターフェイスは、ツリーを調べて、ＬＢＡに対応する論理的−物理的マッピングを得ることができる。従って、例えば、ＮＶＭインターフェイスは、ＬＢＡに対応するツリーのエントリの位置を求め、そしてそのエントリを使用して、ＮＶＭインターフェイスは、どのスーパーブロックがＬＢＡに関連したデータを記憶するか決定する。この決定を行った後、ＮＶＭインターフェイスは、スーパーブロックに関連した１つ以上の有効性カウンタをデクリメントする。その結果、ツリーはメモリにも記憶されているので、アンマッピングプロセスは、メモリアクセスしか含まない。
【００７３】
次いで、ステップ７１８において、ＮＶＭインターフェイスは、ツリーメモリの使用が更新と共に減少する場合にのみアンマップされたＬＢＡを反映するようにツリーを更新する。即ち、ＮＶＭインターフェイスは、更新がツリーの合計エントリ数の正味減少を生じさせる場合だけツリーを更新すると決定する。例えば、データの複数の論理的に隣接するセグメントがアンマップされる（例えば、複数の小さなデータベースエントリが削除される）場合には、ツリーの更新が効果的である。その結果、それらデータセグメントに対応するエントリを平坦化（例えば、合併）し、そして小さなツリーを形成することができ、これは、全体的なツリーメモリ使用を減少させる。又、小さなツリーは、ツリーのサーチを遂行するレートを改善することができる。
【００７４】
対照的に、小さなデータセグメントだけがアンマップされる場合は、ツリーの更新は、それがツリーマッピングを引き裂くならば（例えば、大きなツリーエントリの中間部又は前部がアンマップされるならば）遂行されない。それ故、このツリー更新は、不都合にも、多数のエントリを生じさせる。
【００７５】
ある実施形態において、ＮＶＭインターフェイスは、ＬＢＡに対応するツリーのエントリの位置を求めることにより、アンマップされたＬＢＡを反映するようにツリーを更新する。エントリの位置を求めた後、ＮＶＭインターフェイスは、ＬＢＡに関連したエントリにおける物理的アドレス（例えば、物理的ページアドレス又はバーチャルブロックアドレス）を所定のトークン値へ更新する。
【００７６】
ＮＶＭインターフェイスが、ツリーを調べることによりＬＢＡに対する論理的−物理的マッピングを決定できない（例えば、ツリーメモリがほぼ尽きているか又はシステムがツリーを有していないために論理的−物理的マッピングがツリーに記憶されていない）実施形態では、ＮＶＭインターフェイスは、ＮＶＭから揮発性メモリへインデックスページをロードすることにより論理的−物理的マッピングを決定する必要がある。このシナリオはＮＶＭへのアクセスを伴うが、ＮＶＭのアクセスは、読み取りオペレーションに限定される。プログラムオペレーションとは対照的に、読み取りオペレーションは、一般的に、ガーベージコレクションをトリガーしない。
【００７７】
例えば、図８を参照すれば、有効性カウンタを更新するためのプロセス８００を例示するフローチャートが示されている。プロセス８００は、ステップ８０２で開始し、そしてステップ８０４において、ＮＶＭインターフェイス（例えば、図１のＮＶＭインターフェイス１１８又は図３のＮＶＭインターフェイス３１８）は、ＬＢＡをアンマップするための要求を受け取る。
【００７８】
ステップ８０６へと続いて、ＮＶＭインターフェイスは、揮発性メモリ（例えば、図１のメモリ１１４）に記憶されたビットマップ（例えば、図４Ａ−４Ｃのビットマップ、各々、４００、４０２又は４０４）においてＬＢＡをアンマップする。ステップ８０６は、プロセス７００（図７）のステップ７０４−７１４のような付加的なステップを伴うが、これら付加的なステップは、明瞭化のために、プロセス８００から省略される。
【００７９】
ステップ８０８において、ＮＶＭインターフェイスは、揮発性メモリ（例えば、図１のメモリ１１４）に記憶されたツリー（例えば、図２のツリー２１０）が、ＬＢＡに対応する論理的−物理的マッピングを含むかどうか決定する。ステップ８０８において、ツリーが、ＬＢＡに対応する論理的−物理的マッピングを含むとＮＶＭインターフェイスが決定した場合には、プロセス８００は、ステップ８１０へ進む。
【００８０】
ステップ８１０において、ＮＶＭインターフェイスは、ツリーを使用してＬＢＡに関連したＮＶＭの１つ以上のスーパーブロックを決定する。
【００８１】
次いで、ステップ８１２において、ＮＶＭインターフェイスは、スーパーブロックに関連した少なくとも１つの有効性カウンタをデクリメントし、ここで、少なくとも１つの有効性カウンタは、揮発性メモリに記憶されている。１つ以上のスーパーブロックがツリーを使用して決定されるので、ＮＶＭインターフェイスは、ＮＶＭに記憶されたインデックスページの読み取り又は書き込みを遂行する必要はない。これは、ガーベージコレクションがトリガーされる確率を下げる上で助けとなる。プロセス８００は、次いで、ステップ８１４で終了となる。
【００８２】
ステップ８０８へ戻ると、ツリーがＬＢＡに対応する論理的−物理的マッピングを含まないとＮＶＭインターフェイスが決定した場合には、プロセス８００は、ステップ８１６へ進む。ステップ８１６において、ＮＶＭインターフェイスは、ＬＢＡに関連したインデックスページ（例えば、図２のインデックスページ１−Ｎの１つ）をＮＶＭ（例えば、図１のＮＶＭ１２０又は図３のＮＶＭ３２０）からロードする。例えば、ＮＶＭインターフェイスは、インデックスページをインデックステーブルキャッシュ（例えば、図２のインデックステーブルキャッシュ２０４）にロードする。
【００８３】
ステップ８１８へ続くと、ＮＶＭインターフェイスは、ロードされたインデックスページを調べることにより、ＬＢＡに関連したＮＶＭの１つ以上のスーパーブロックを決定する。次いで、ステップ８１２において、ＮＶＭインターフェイスは、１つ以上のスーパーブロックに関連した少なくとも１つの有効性カウンタをデクリメントする。従って、ＮＶＭインターフェイスは、このシナリオではインデックスページを読み取る必要はあるが、ＮＶＭにおいてインデックスページを更新し及び再プログラムする必要はない。その正味の結果として、インデックスページの合計アクセス数を依然減少することができ、ガーベージコレクションを回避することができる。次いで、プロセス８００は、ステップ８１４で終了となる。
【００８４】
論理的−物理的マッピングがツリーに維持されず（又は完全に維持されず）、むしろ、ＮＶＭに記憶されたインデックスページ（例えば、図２のインデックスページ１−Ｎ）に維持される実施形態では、ビットマップを維持することで、ガーベージコレクションプロセスを改善することもできる。特に、ビットマップを使用すると、ＮＶＭインターフェイスは、ガーベージコレクション中に行う必要のあるインデックスペースアクセスの回数を減少することができる。
【００８５】
例えば、図９を参照すれば、高速ガーベージコレクションのためのプロセス９００を例示するフローチャートが示されている。プロセス９００は、ステップ９０２で開始し、そしてステップ９０４において、ＮＶＭインターフェイス（例えば、図１のＮＶＭインターフェイス１１８又は図３のＮＶＭインターフェイス３１８）は、ＮＶＭのデータブロック（例えば、図２のデータブロック１−Ｎの１つ）においてガーベージコレクションを遂行すると決定する。
【００８６】
ステップ９０６へと続いて、ＮＶＭインターフェイスは、データブロックに記憶されたブロックＴＯＣ（例えば、図２のブロックＴＯＣ  １−Ｎの１つ）をロードする。次いで、ステップ９０８において、ＮＶＭインターフェイスは、揮発性メモリに記憶されたビットマップ（例えば、図４Ａ−４Ｃのビットマップ、各々、４００、４０２又は４０４）をブロックＴＯＣと比較する。
【００８７】
ステップ９１０において、ＮＶＭインターフェイスは、その比較に基づいてマップされるデータブロックの論理的アドレス（例えば、ＬＢＡ）のサブセットを決定する。例えば、ビットマップを使用して、ＮＶＭインターフェイスは、どのＬＢＡがアンマップされるか決定する。それ故、それらのアンマップされたＬＢＡは、ガーベージコレクションプロセスから除外される。
【００８８】
ステップ９１２へと続いて、ＮＶＭインターフェイスは、論理的アドレスのサブセットに関連したデータブロックに記憶されたユーザデータのみに対してガーベージコレクションを遂行する。ガーベージコレクションは、システムに基づいて種々の仕方で遂行することができる。例えば、システムがツリーを維持しない実施形態では、ＮＶＭインターフェイスは、論理的アドレスのサブセットに対応するＮＶＭに記憶されたインデックスページのみにアクセスすることによりユーザデータの位置を求めることができる。従って、論理的アドレスのサブセットのうちの各論理的アドレスに対して、ＮＶＭインターフェイスは、その論理的アドレスに関連したインデックスページ（例えば、図２のインデックスページ１−Ｎの１つ）にアクセスする。次いで、インデックスページに基づき、ＮＶＭインターフェイスは、論理的アドレスに対応するデータブロックの物理的アドレスを決定することができる。物理的アドレスを決定した後に、ＮＶＭインターフェイスは、物理的アドレスからＮＶＭの異なるデータブロックへユーザデータをコピーすることができる。
【００８９】
揮発性メモリにツリー（例えば、図２のツリー２１０）が記憶される実施形態では、ＮＶＭインターフェイスは、そのツリーが論理的アドレスのサブセットに対する論理的−物理的マッピングを含むかどうか決定する。例えば、論理的アドレスのサブセットのうちの各論理的アドレスに対して、ＮＶＭインターフェイスは、ツリーを調べて、その論理的アドレスに対して論理的−物理的マッピングが存在するかどうか決定する。その論理的アドレスに対して論理的−物理的マッピングが存在しないとＮＶＭインターフェイスが決定した場合には、ＮＶＭインターフェイスは、その論理的アドレスに関連したインデックスページにアクセスすることができる。次いで、上述したように、インデックスページに基づいて、ＮＶＭインターフェイスは、その論理的アドレスに対応するデータブロックの物理的アドレスを決定する。物理的アドレスを決定した後、ＮＶＭインターフェイスは、その物理的アドレスからＮＶＭの異なるデータブロックへユーザデータをコピーする。
【００９０】
しかしながら、論理的アドレスに対して論理的−物理的マッピングが存在するとＮＶＭインターフェイスが決定した場合には、ＮＶＭインターフェイスは、ツリーを使用して、論理的アドレスに対応するデータブロックの物理的アドレスを決定する。次いで、ＮＶＭインターフェイスは、その物理的アドレスからＮＶＭの異なるデータブロックへユーザデータをコピーする。ガーベージコレクションを遂行した後、プロセス９００は、ステップ９１４で終了となる。
【００９１】
従って、ビットマップを使用して、ＮＶＭにおいて検査される必要のある論理的アドレスの数を減少することにより、ガーベージコレクション中に遂行される必要のあるＮＶＭオペレーションの数を対応的に減少することができる。その結果、ガーベージコレクションプロセスをより効率的に遂行することができる。
【００９２】
更に、揮発性メモリに記憶されたツリーに論理的−物理的マッピングが完全に維持される実施形態では、ビットマップも維持することで、ガーベージコレクションプロセスを最低限改善することができる。論理的アドレスのサブセットのみに対してツリーを調べることにより、メモリアクセスの量を減少することができる。
【００９３】
図５−９のプロセス５００、６００、７００、８００及び９００は、システムの１つ以上のコンポーネント（例えば、図１の電子装置１００又は図３の電子装置３００）により実行されることを理解されたい。例えば、プロセスにおけるステップの少なくとも幾つかは、ＮＶＭインターフェイス（例えば、図１のＮＶＭインターフェイス１１８又は図３のＮＶＭインターフェイス３１８）によって遂行される。当業者であれば、ステップの１つ以上は、コントロール回路（例えば、図１のＳｏＣコントロール回路１１２）により遂行されることが明らかであろう。
【００９４】
更に、図５−９のプロセス５００、６００、７００、８００及び９００は、単なる例示に過ぎないことを理解されたい。本発明の範囲から逸脱せずに、いずれかのステップを除去し、変更し又は組み合わせることもできるし、付加的なステップを追加することもできる。
【００９５】
以上に述べた本発明の実施形態は、例示に過ぎず、それに限定されない。
【符号の説明】
【００９６】
１００：電子装置
１１０：システムオンチップ
１１２：ＳｏＣコントロール回路
１１４：メモリ
１１８：ＮＶＭインターフェイス
１２０：不揮発性メモリ（ＮＶＭ）
２００：メモリマッピングアーキテクチャー
２０２：ルックアップテーブル
２０４：インデックステーブルキャッシュ
２０６：インデックステーブル
２０８：データページ
２１０：ツリー
２１２：ビットマップ
３００：電子装置
３１０：ファイルシステム
３１２：ＮＶＭドライバ
３１４：変換層
３１６：ＮＶＭバスコントローラ
３２０：ＮＶＭ
４００：ビットマップ
４００Ａ−Ｈ：エントリ
４０２：ビットマップ
４０２Ａ−Ｈ：エントリ
４０４：ビットマップ
４０４Ａ−Ｈ：エントリ
【図１】
2013137770.tif 000003
【図２】
2013137770.tif 000004
【図３】
2013137770.tif 000005
【図４Ａ】
2013137770.tif 000006
【図４Ｂ】
2013137770.tif 000007
【図４Ｃ】
2013137770.tif 000008
【図５】
2013137770.tif 000009
【図６】
2013137770.tif 000010
【図７】
2013137770.tif 000011
【図８】
2013137770.tif 000012
【図９】
2013137770.tif 000013
【外国語明細書】
2013137770.tif 000014
2013137770.tif 000015
2013137770.tif 000016
2013137770.tif 000017
2013137770.tif 000018
2013137770.tif 000019
2013137770.tif 000020
2013137770.tif 000021
2013137770.tif 000022
2013137770.tif 000023
2013137770.tif 000024
2013137770.tif 000025
2013137770.tif 000026
2013137770.tif 000027
2013137770.tif 000028
2013137770.tif 000029
2013137770.tif 000030
2013137770.tif 000031
2013137770.tif 000032
2013137770.tif 000033
2013137770.tif 000034
2013137770.tif 000035
2013137770.tif 000036
2013137770.tif 000037
2013137770.tif 000038
2013137770.tif 000039
2013137770.tif 000040
2013137770.tif 000041
2013137770.tif 000042
2013137770.tif 000043
2013137770.tif 000044
2013137770.tif 000045
2013137770.tif 000046
2013137770.tif 000047
2013137770.tif 000048
2013137770.tif 000049
2013137770.tif 000050
2013137770.tif 000051
2013137770.tif 000052
2013137770.tif 000053
2013137770.tif 000054
2013137770.tif 000055
2013137770.tif 000056
2013137770.tif 000057
2013137770.tif 000058
2013137770.tif 000059
2013137770.tif 000060
2013137770.tif 000061