(57)【要約】      （修正有）【課題】ｉｎｏｄｅの割り当て及び割り当て解除の方法及びコンピュータプログラムを提供する。【解決手段】第１のｉｎｏｄｅテーブルのすべてのｉｎｏｄｅが初期化済みであるか否かを判断する。第１のｉｎｏｄｅテーブルのすべてのｉｎｏｄｅが初期化済みであるとの判断に応答して、追加のｉｎｏｄｅを割り当てるさらなるｉｎｏｄｅテーブルを作成する。ｉｎｏｄｅテーブルのディスクブロックアドレスを指し示すｉｎｏｄｅマップを作成する。【選択図】図４
2009064417.tif 000002
【特許請求の範囲】
【請求項１】
第１のｉｎｏｄｅテーブルを含むコンピューティングファイルシステムにおいてｉｎｏｄｅを割り当てる方法であって、
前記第１のｉｎｏｄｅテーブルのすべてのｉｎｏｄｅが初期化済みであるか否かを判断するステップと、
前記第１のｉｎｏｄｅテーブルのすべてのｉｎｏｄｅが初期化済みであるとの判断に応答して、追加のｉｎｏｄｅを割り当てるさらなるｉｎｏｄｅテーブルを作成するステップと
を含む方法。
【請求項２】
前記さらなるｉｎｏｄｅテーブルのすべてのｉｎｏｄｅが初期化済みであるときに、少なくとも１つの追加のｉｎｏｄｅテーブルを作成するステップ
をさらに含む請求項１に記載の方法。
【請求項３】
１つまたは２つ以上のｉｎｏｄｅマップ（複数可）を提供するステップをさらに含み、
前記ｉｎｏｄｅマップ（複数可）は、選択され、割り当てられたｉｎｏｄｅを含む前記ｉｎｏｄｅテーブルのディスクブロックアドレスを指し示す
請求項１に記載の方法。
【請求項４】
各前記ｉｎｏｄｅテーブルにおけるｉｎｏｄｅの個数は、ディスク空間の総量と、各前記ｉｎｏｄｅマップで参照されるｉｎｏｄｅテーブルアドレスの個数との関数である
請求項３に記載の方法。
【請求項５】
ファイルシステムの作成中にｉｎｏｄｅの個数を求めるステップをさらに含む
請求項４に記載の方法。
【請求項６】
少なくとも第１のｉｎｏｄｅテーブルとさらなるｉｎｏｄｅテーブルを含むコンピューティングファイルシステムにおいてｉｎｏｄｅを割り当て解除する方法であって、
前記さらなるｉｎｏｄｅテーブルが、初期化されたｉｎｏｄｅを含まないかを判断するステップと、
前記さらなるテーブルが初期化されたｉｎｏｄｅを含まないとの判断に応答して、前記さらなるｉｎｏｄｅテーブルを削除するステップと
を含む方法。
【請求項７】
前記さらなるｉｎｏｄｅテーブルに関連付けられているｉｎｏｄｅマップにおける前記さらなるｉｎｏｄｅテーブルの参照子を削除するステップをさらに含む
請求項６に記載の方法。
【請求項８】
前記さらなるテーブルが前記ｉｎｏｄｅマップによって参照される唯一のテーブルであるとの判断に応答して、前記さらなるテーブルに関連付けられている前記ｉｎｏｄｅマップを削除するステップ
をさらに含む請求項７に記載の方法。
【請求項９】
第１のｉｎｏｄｅテーブルを含むコンピュータファイルシステムにおいてｉｎｏｄｅを割り当てるコンピュータプログラムであって、コンピューティングシステムのコンピュータ可読媒体上で実施されると、
前記第１のｉｎｏｄｅテーブルのすべてのｉｎｏｄｅが初期化済みであるか否かを判断するステップと、
前記第１のｉｎｏｄｅテーブルのすべてのｉｎｏｄｅが初期化済みであるとの判断に応答して、追加のｉｎｏｄｅを提供するさらなるｉｎｏｄｅテーブルを作成するステップと
を前記コンピューティングシステムに実施させる少なくとも１つの命令を含むコンピュータプログラム。
【請求項１０】
前記さらなるｉｎｏｄｅテーブルのすべてのｉｎｏｄｅが初期化済みであるときに、少なくとも１つの追加のｉｎｏｄｅテーブルを作成するステップをさらに実施するように構成されている
請求項９に記載のコンピュータプログラム。
【請求項１１】
前記コンピュータプログラムは、１つまたは２つ以上のｉｎｏｄｅマップ（複数可）を提供するステップをさらに実施するように構成され、
前記ｉｎｏｄｅマップ（複数可）は、選択され、割り当てられたｉｎｏｄｅを含む前記ｉｎｏｄｅテーブルのディスクブロックアドレスを指し示す
請求項９に記載のコンピュータプログラム。
【請求項１２】
各前記ｉｎｏｄｅテーブルにおけるｉｎｏｄｅの個数は、ディスク空間の総量と、各前記ｉｎｏｄｅマップで参照されるｉｎｏｄｅテーブルアドレスの個数との関数である
請求項１１に記載のコンピュータプログラム。
【請求項１３】
ファイルシステムの作成中にｉｎｏｄｅの個数を求めるステップをさらに実施するように構成されている
請求項１２に記載のコンピュータプログラム。
【請求項１４】
少なくとも第１のｉｎｏｄｅテーブルとさらなるｉｎｏｄｅテーブルを含むコンピュータファイルシステムにおいてｉｎｏｄｅを割り当て解除するコンピュータプログラムであって、コンピューティングシステムのコンピュータ可読媒体上で実施されると、
前記さらなるｉｎｏｄｅテーブルが初期化されたｉｎｏｄｅを含まないかを判断するステップと、
前記さらなるｉｎｏｄｅテーブルが初期化されたｉｎｏｄｅを含まないとの判断に応答して、前記さらなるｉｎｏｄｅテーブルを削除するステップと
を前記コンピューティングシステムに実施させる少なくとも１つの命令を含むコンピュータプログラム。
【請求項１５】
前記さらなるｉｎｏｄｅテーブルに関連付けられているｉｎｏｄｅマップにおける前記さらなるｉｎｏｄｅテーブルの参照子を削除するステップをさらに実施するように構成されている
請求項１４に記載のコンピュータプログラム。
【請求項１６】
前記さらなるテーブルが前記ｉｎｏｄｅマップによって参照される唯一のテーブルであるとの判断に応答して、前記さらなるテーブルに関連付けられている前記ｉｎｏｄｅマップを削除するステップをさらに実施するように構成されている
請求項１５に記載のコンピュータプログラム。
【請求項１７】
請求項９に記載のコンピュータプログラムを記憶したコンピュータ可読媒体。
【請求項１８】
請求項１４に記載のコンピュータプログラムを記憶したコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施の形態は、ｉｎｏｄｅの割り当ておよび割り当て解除の方法およびコンピュータプログラムに関する。
【背景技術】
【０００２】
ｉｎｏｄｅは、ファイル、ディレクトリ、又は他のファイルシステムオブジェクトについての基本的なメタデータを記憶するために、多くのファイルシステムによって利用されるデータ構造である。ｉｎｏｄｅを利用するファイルシステムの例には、数ある中でも、ＵＮＩＸ（登録商標）ファイルシステム（ＵＦＳ）、Ｖｅｒｉｔａｓファイルシステム（ＶｘＦＳ）、及びＥＸＴ２ファイルシステムが含まれる。
【０００３】
ｉｎｏｄｅは、ファイルシステム作成中にｉｎｏｄｅテーブルで事前に割り当てられると共に、事前に初期化される。ファイルシステムは、ファイルシステムパーティションのサイズ及び平均ファイルサイズを考慮するアルゴリズムを使用することによって、ｉｎｏｄｅテーブルに設けられるｉｎｏｄｅの個数を計算する。ファイルシステムは、次に、ディスク空間の連続ブロック（すなわち、ｉｎｏｄｅテーブル）の固定オフセットにｉｎｏｄｅを記憶する。この連続ブロックは、実際のデータを記憶するのに使用されるディスク空間の部分とは異なる。ＵＮＩＸ（登録商標）ファイルシステムでは、ｉｎｏｄｅ番号をオフセットとして直接使用してｉｎｏｄｅをフェッチすることを可能にするために、ｉｎｏｄｅはｉｎｏｄｅテーブルに連続した順序で記憶される。すなわち、ｉｎｏｄｅ番号は、ｉｎｏｄｅのディスクブロックアドレス（すなわち、ｉｎｏｄｅテーブルにおけるｉｎｏｄｅのロケーション）へ直接マッピングされる。
【０００４】
ファイルシステムが作成されると、ｉｎｏｄｅテーブルにおけるｉｎｏｄｅの個数は増加させることも減少させることもできない。すなわち、ｉｎｏｄｅテーブルは固定される。ファイルシステムは多くの場合、ｉｎｏｄｅテーブルにおける利用可能なすべてのｉｎｏｄｅを最終的には利用し得る多くの小さなファイルを記憶するようにプログラミングされたアプリケーションを含み、それによって、たとえ利用可能なディスク空間が存在しても、他のアプリケーションがさらなるファイルを記憶することを防止する。代替形態では、ファイルシステムは過剰なｉｎｏｄｅを事前に割り当てる場合があり、その結果、ファイルシステムは、ファイルシステムの作成中に不要な処理オペレーションを実行する。これは特に、ファイルシステムが少数の大きなファイルを記憶する常駐アプリケーションを有する場合である。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明は、ｉｎｏｄｅの割り当ておよび割り当て解除のための方法およびプログラムなどを提供する。
【課題を解決するための手段】
【０００６】
本発明の一形態は、第１のｉｎｏｄｅテーブルを含むコンピューティングファイルシステムにおいてｉｎｏｄｅを割り当てる方法であって、前記第１のｉｎｏｄｅテーブルのすべてのｉｎｏｄｅが初期化済みであるか否かを判断するステップと、前記第１のｉｎｏｄｅテーブルのすべてのｉｎｏｄｅが初期化済みであるとの判断に応答して、追加のｉｎｏｄｅを割り当てるさらなるｉｎｏｄｅテーブルを作成するステップとを含む方法である。
【０００７】
次に、本発明をより明確に確認することができるようにするために、例として、添付図面を参照して実施形態を説明する。
【発明を実施するための最良の形態】
【０００８】
コンピューティングファイルシステムでｉｎｏｄｅの割り当て及び割り当て解除を行う方法及びコンピュータプログラムが提供される。
【０００９】
一実施形態では、ｉｎｏｄｅを割り当てる方法は、コンピューティングファイルシステムに設けられた第１のｉｎｏｄｅテーブルのすべてのｉｎｏｄｅが初期化されているか否かを判断するステップと、第１のｉｎｏｄｅテーブルのすべてのｉｎｏｄｅが初期化されているとの判断に応じて、追加のｉｎｏｄｅを割り当てるさらなるｉｎｏｄｅテーブルを作成するステップとを含む。
【００１０】
別の実施形態では、コンピューティングシステムのコンピュータ可読媒体上で実施されると、上述したｉｎｏｄｅ割り当て方法ステップをコンピューティングシステムに実施させる少なくとも１つの命令を含むコンピュータプログラムが提供される。
【００１１】
別の実施形態では、少なくとも第１のｉｎｏｄｅテーブル及びさらなるｉｎｏｄｅテーブルを含むコンピューティングファイルシステムにおいてｉｎｏｄｅを割り当て解除する方法であって、さらなるｉｎｏｄｅテーブルが、初期化されたｉｎｏｄｅを含まないかを判断するステップと、さらなるテーブルが初期化されたｉｎｏｄｅを含まないと判断されたことに応答して、さらなるｉｎｏｄｅテーブルを削除するステップとを含む方法が提供される。
【００１２】
別の実施形態では、コンピューティングシステムのコンピュータ可読媒体上で実施されると、上述したｉｎｏｄｅ割り当て解除方法ステップをコンピューティングシステムに実施させる少なくとも１つの命令を含むコンピュータプログラムが提供される。
【００１３】
本明細書の文脈において、「ｉｎｏｄｅテーブル」という語句は、その範囲内に、任意の適したディスク空間に記憶することができ、初期化又は初期化解除（de-initialize）のいずれかを行うことができる少なくとも１つのｉｎｏｄｅを含む任意のテーブルを含む。
【００１４】
また、図１に示すクライアント−サーバコンピューティングシステム１００等のコンピューティングシステムも提供される。このクライアント−サーバコンピューティングシステム１００は、上述した方法を実施するように構成されている。一実施形態では、クライアント−サーバコンピューティングシステム１００は、インターネットの形態のネットワーク１０６を介してクライアント１０４に接続されているサーバ１０２を備える。クライアント１０４は、サーバ１０２と通信する標準的なハードウェア及びソフトウェアを備えるパーソナルコンピューティングデバイス１０４ａ、１０４ｂの形態を有する。クライアント１０４は、伝送制御プロトコル／インターネットプロトコル（ＴＣＰ／ＩＰ）のプロトコルスイートを使用してサーバ１０２と通信する。ストレージデバイス１０８もネットワーク１０６に接続されている。
【００１５】
図２を参照すると、サーバ１０２のハードウェア及びソフトウェアのブロック図が示されている。サーバ１０２は、説明する実施形態によれば、Hewlett Packard社から入手可能なＨＰ−ＵＸ  ｒｘ５６７０サーバの形態を有する。サーバ１０２は、ＵＮＩＸ（登録商標）スタックを有するＵＮＩＸ（登録商標）オペレーティングシステムの形態のオペレーティングシステムを実行する。この実施形態では、サーバ１０２はＵＮＩＸ（登録商標）オペレーティングシステムを実施するが、他の実施形態は、たとえばＬＩＮＵＸオペレーティングシステム等の異なるオペレーティングシステムを含むことができることに留意すべきである。
【００１６】
ＵＮＩＸ（登録商標）オペレーティングシステムは、Ｕｎｉｘ（登録商標）ファイルシステム（ＵＦＳ）の形態のファイルシステムも含む。ＵＦＳは、シリンダグループの集まりから成り、ネットワーク１０６とハードディスク１２２との間のデータの転送を制御するソフトウェアを含む。メモリ１１８の一部から成るバッファキャッシュは、このデータ転送用のバッファとして使用される。また、バッファキャッシュは、頻繁に起こる待ち時間の大きなディスクＩ／Ｏを削減する目的でディスクブロックのコンテンツを保持するようにも構成されている。
【００１７】
サーバ１０２はさらに、システムバス１１４に結合されるクアドＩｎｔｅｌ  Ｉｔａｎｉｕｍ  ２プロセッサ１１２ａ、１１２ｂ（米国のIntel社から入手可能、http://www.intel.com/）の形態の複数のプロセッサ１１２も含む。メモリコントローラ／キャッシュ１１６もシステムバス１１４に結合され、ダブルデータレートＤＤＲ  ＳＤＲＡＭの形態を有するメモリ１１８をインターフェースするように構成されている。また、Ｉ／Ｏバス１２６経由でＩ／Ｏバスブリッジ１２４に接続されている、高速グラフィックアドレス指定をハンドリングするグラフィックスアダプタ１２０及びＡＴＡギガバイトハードディスク１２２も設けられている。メモリコントローラ１１６及びＩ／Ｏバスブリッジは、図２に示すように相互接続することができる。
【００１８】
Ｉ／Ｏバス１２６には、ＰＣＩバス１３０ａ、１３０ｂ、１３０ｃを介してサーバ１０２に接続されるデバイスへのインターフェースを提供するＰＣＩバスブリッジ１２８ａ、１２８ｂ、１２８ｃが接続されている。モデム１３２及びネットワークアダプタ１３４は、ＰＣＩバス１３０ａに結合されている。ネットワークアダプタ１３４は、サーバ１０２がＴＣＰ／ＩＰプロトコルを使用してクライアント１０４とデータを交換することを可能にするように構成されている。当業者によって認識されるように、ＣＤ−ＲＯＭ等の追加のＩ／Ｏデバイスも、Ｉ／Ｏバス１３０ａ、１３０ｂ、１３０ｃを介してサーバ１０２に結合することができる。
【００１９】
上述したように、ＵＦＳは、サーバ１０２のハードディスク１２２を複数のシリンダグループに分割する。従来のＵＦＳディスクレイアウトでは、各シリンダグループは、ファイルシステムスーパーブロックのバックアップコピーと、グループヘッダ（統計値、フリーリスト、及びそのシリンダグループを記述する他の情報を含む）と、一定の個数の事前に割り当てられると共に事前に初期化されているｉｎｏｄｅを含むｉｎｏｄｅテーブルとから成る。ｉｎｏｄｅテーブルのサイズは、ファイルシステム作成中（すなわち、コマンドｍｋｆｓがＵＦＳオペレーティングシステムで起動された時）に、ファイルパーティションのサイズ及び平均ファイルサイズに基づいて計算される。従来のシリンダディスクレイアウトを図３に示す。
【００２０】
本発明の実施形態は、ファイルシステムによる要求に応じて、（通常は、別のｉｎｏｄｅテーブル又は追加のｉｎｏｄｅテーブルと呼ばれるブロックで）追加のｉｎｏｄｅを割り当てる動的なｉｎｏｄｅ割り当て方法を利用する。追加のｉｎｏｄｅは、初期ファイルシステム作成後に割り当てることができるので、最初に割り当てられるｉｎｏｄｅの個数は、従来のファイルシステムによって必要とされるものよりも大幅に少なくすることができる。この方法論は、ファイルシステムが、現在割り当てられているｉｎｏｄｅの個数をもはや必要としない場合に、ｉｎｏｄｅを割り当て解除することもできる。
【００２１】
次に、図４のフロー図を参照して、第１のｉｎｏｄｅテーブルを含むコンピューティングファイルシステムのｉｎｏｄｅ割り当て方法を本発明の一実施形態に従って説明する。説明する実施形態では、第１のｉｎｏｄｅテーブルはファイルシステムを作成する時に作成され、第１のｉｎｏｄｅテーブルのｉｎｏｄｅは常駐アプリケーションによる要求に応じて初期化される。ステップ４０２において、第１のｉｎｏｄｅテーブルのすべてのｉｎｏｄｅが初期化済みであるか否かについての判断が行われる。ステップ４０４において、ファイルシステムによって必要とされるｉｎｏｄｅの個数が第１のｉｎｏｄｅテーブルの容量を超えている（すなわち、第１のｉｎｏｄｅテーブルのすべてのｉｎｏｄｅが初期化済みである）と判断された場合には、追加のｉｎｏｄｅを割り当てるさらなるｉｎｏｄｅテーブルが作成される。後続の段落でより詳細に説明するように、利用可能なディスク空間の量にのみ応じて、任意の個数のさらなるｉｎｏｄｅテーブル／追加のｉｎｏｄｅテーブルをこの方法で作成でき、任意の適したディスクロケーションに記憶することができることが容易に理解されよう。
【００２２】
常駐アプリケーションが所望のｉｎｏｄｅを突き止めることを可能にするために、ステップ４０６において、ｉｎｏｄｅマップの形態のデータ構造（以下、「alloc_map」と呼ぶ）が作成される。alloc_mapは、実質的には、連続したｉｎｏｄｅテーブル（以下、「inode_chunk（ｉｎｏｄｅチャンク）」）を指し示すディスクブロックアドレスのアレイである。図６は、alloc_mapの一般的な構造を示している。図示するように、alloc_mapのｎ番目のエントリーは、（ｎ×inodechunksize）〜（（（ｎ＋１）×inodechunksize）−１）の番号が付けられたｉｎｏｄｅを含むinode_chunkを指し示す。一方、マップを１つだけ使用すると、ｉｎｏｄｅは（allocmapsize）×（inodechunksize）に制限される。したがって、必要な場合に、割り当てられたすべてのｉｎｏｄｅを参照するために、さらなるalloc_mapを作成することができる。拡張されたallloc_map又はinode_chunkに必要なディスク空間は、ファイルシステムによって事前に確保しておく必要はない。
【００２３】
図５は、上述した方法をより詳細に示している。簡単にするために、図５を参照して説明する方法論は、各alloc_mapが４つのinode_chunkのディスクアドレスを指し示すように構成されることを提供する。ファイルシステムの作成中に、第１のalloc_map５０２及び第１のinode_chunk５０４のみが割り当てられる。図示するように、alloc_map５０２の最初のエントリーは第１のinode_chunk５０４を指し示す。ｉｎｏｄｅの個数が、第１のinode_chunk５０４の容量を超えると、さらなるinode_chunk５０６が割り当てられる。同様に、alloc_map５０２の容量を超えると（ここでは、さらなるinode_chunk５１０が割り当てられると）、新しいalloc_map５０８が割り当てられ、前のalloc_map５０２にリンクされる。
【００２４】
上記で概説した方法論を使用してｉｎｏｄｅを取り出すのに使用することができる擬似コンピュータプログラマブルコードの一例を以下に提供する。
IGET (inode_number) ：ｉｎｏｄｅを返す
{
inode_chunk_number = inode_number / chunksize
alloc_map_number = inode_chunk_number / allocmapsize
if (alloc_map_numberに対応するalloc_mapが存在しない)
{
＊サイズallocmapsizeの新しいalloc_mapを割り当てる
＊alloc_mapのエントリーを適切に初期化する
＊このalloc_mapを前のalloc_map及び次のalloc_mapにリンクする
}
if (inode_chunk_numberに対応するinode_chunkが存在しない)
{
＊サイズchunksizeのinode_chunkを割り当てる
＊alloc_mapの（inode_chunk_number % allocmapsize）番目のエントリーを、このinode_chunkの開始アドレスに初期化する
}
＊オフセット（inode_chunk_number % allocmapsize）におけるalloc_mapからinode_chunkの開始アドレスを得る
＊オフセット（inode_number % chunksize）におけるinode_chunkから、必要とされるｉｎｏｄｅをフェッチし、このｉｎｏｄｅを返す
}
【００２５】
以下の式１は、上述した方法を使用してｉｎｏｄｅをフェッチするための全時間を求めるのに使用される。示すように、このデータは、その後、最も適切なinode_chunk及びalloc_mapサイズを確立するためにファイルシステムにより利用することができる。
Ｔ＝Ｔｃａ＋Ｔｃｉ＋Ｔｓａ＋Ｔａａ＋Ｔｉａ＋Ｔｓｉｃ＋Ｔａｉ＋Ｔｉｉ＋Ｔｓｉ
（式１）
式中、
Ｔｃａ＝alloc_map数を計算するための時間
Ｔｃｉ＝inode_chunk数を計算するための時間
Ｔｓａ＝必要とされるalloc_mapを検索してフェッチするための時間
Ｔａａ＝新しいalloc_mapを割り当てるための時間
Ｔｉａ＝alloc_mapを初期化するための時間
Ｔｓｉｃ＝必要とされるinode_mapを検索してフェッチするための時間
Ｔａｉ＝新しいinode_chunkを割り当てるための時間
Ｔｉｉ＝inode_chunkを初期化するための時間
Ｔｓｉ＝inode_chunkから、必要とされるｉｎｏｄｅを検索してフェッチするための時間
【００２６】
式１において、Ｔｃａ及びＴｃｉは共に一定時間であり（すなわち、ディスクアクセスを必要としない）、したがって、Ｋｃａ及びＫｃｉによってそれぞれ表すことができる。また、（alloc_map及びinode_chunkについての）新しいディスクブロックの割り当て及び初期化は、スーパーブロックを更新するためにそれぞれ１回しかディスクアクセスを必要としない（これは、スーパーブロックの「インメモリ」コピーのみを変更することによって回避することもできる）。したがって、これらの時間（すなわち、Ｔａａ、Ｔｉａ、Ｔａｉ、及びＴｉｉ）は、定数Ｋａａ、Ｋｉａ、Ｋａｉ、及びＫｉｉによってそれぞれ表すことができる。alloc_mapを検索するステップはalloc_mapの個数に正比例する。ｎをファイルシステムにおけるalloc_mapの個数とすると、alloc_mapを検索するプロセスはｎ回のディスクアクセスを必要とする。すなわち、Ｔｓａ＝ｎ×Ｋｓａである。ここで、Ｋｓａは、１つのalloc_mapをフェッチするのに必要な時間を表す定数である。次に、Ｔｓｉｃ及びＴｓｉも（アルゴリズムで示されるように）一定時間のオペレーションである。これらをＫｓｉｃ及びＫｓｉによってそれぞれ表すものとする。
【００２７】
したがって、アルゴリズムによって必要とされる全時間は、
Ｔ＝（Ｔｃａ＋Ｔｃｉ）＋（Ｔｓｉｃ＋Ｔｓｉ）＋（Ｔａａ＋Ｔｉａ＋Ｔａｉ＋Ｔｉｉ）＋Ｔｓａ
＝Ｋ＋ｎ×Ｋｓａ（簡単にするためにすべての定数の合計をＫによって置き換える）
となる。
【００２８】
したがって、このアルゴリズムの時間計算量は、
Ｏ（Ｔ）＝Ｏ（Ｋ）＋Ｏ（ｎ×Ｋｓａ）
近似値＝Ｏ（ｎ）  （Ｋ及びＫｓａは定数であるので）
となる。
【００２９】
すなわち、本明細書で説明したアルゴリズムの性能オーバーヘッドは、alloc_mapの個数に関する一次方程式である。性能は、ｎの値が非常に大きい場合（＞１００）には劣化する可能性があるが、alloc_map及びinode_chunkの双方のサイズ（ファイルシステムの作成時に設定される）は、アルゴリズムの性能に対する影響を回避するために、ファイルシステムサイズの関数として計算される。一般に、alloc_mapの個数（ｎ）は、４を超える必要はない。
【００３０】
たとえば、１テラバイトのサイズのファイルシステムを考え、alloc_mapのサイズを１メガバイトと考え、inode_chunkのサイズを５１２キロバイトと考える。８バイトのアドレスを仮定すると、単一のalloc_mapは、２１７個のinode_chunkのアドレスを保持することができる。たとえinode_chunkが、５１２個のｉｎｏｄｅしか保持することができなくても、（２１７）×（２９）＝（２２６）個のｉｎｏｄｅをハンドリングするのに、単一のalloc_mapで十分である。したがって、４つのalloc_map（２２８）を使用することによって、２６８４３５４５６個のｉｎｏｄｅが提供される。これは、ほとんどの実際のシナリオにとって十分な大きさである。
【００３１】
本明細書で説明した実施形態は、ｉｎｏｄｅテーブルの割り当ての方法を説明しているが、この方法は、複数のｉｎｏｄｅテーブル（すなわち、第１のｉｎｏｄｅテーブル及びさらなるｉｎｏｄｅテーブル又は追加のｉｎｏｄｅテーブル）を含むコンピューティングファイルシステムにおいて、ｉｎｏｄｅ及びｉｎｏｄｅテーブルの割り当て解除（又は削除）も同様にすることができることに留意されたい。ファイルシステムのファイルが削除されると、対応するｉｎｏｄｅはｉｎｏｄｅ初期化解除コードによって初期化解除され、それによって、別のファイルがそのｉｎｏｄｅを使用することが可能になる。初期化解除されているｉｎｏｄｅが関連付けられたｉｎｏｄｅテーブルに残っている最後のｉｎｏｄｅであるとｉｎｏｄｅ初期化解除コードが判断した場合には、そのコードパスは、ｉｎｏｄｅテーブル全体を割り当て解除（すなわち、削除）し、それに従って、関連付けられたｉｎｏｄｅマップを更新する。
【００３２】
割り当て方法及び割り当て解除方法の実施形態は、コンピューティングシステムのコンピュータ可読媒体上で実施されると上述した方法ステップをコンピューティングシステムに実施させる命令を含むコンピュータプログラム（ハードウェア、ソフトウェア、又はこの２つの組み合わせのいずれかによる）によって実施することができる。
【００３３】
必須ではないが、このコンピュータプログラムは、開発者による使用のために、アプリケーションプログラミングインターフェース（ＡＰＩ）を介して実施される場合があり、別のソフトウェアアプリケーション内のコードで実施することができる。一般に、ソフトウェアアプリケーションは、特定の機能を実行するか又は特定の機能の実行を助けるルーチン、プログラム、オブジェクト、コンポーネント、及びデータファイルを含むので、ソフトウェアアプリケーションを、複数のルーチン、オブジェクト、及びコンポーネントにわたって分散させることができるが、実施形態及び本明細書で権利を主張するより広い発明と同じ機能を達成することができることが理解されよう。このような変形及び変更は、当業者の理解の範囲内にあるであろう。
【００３４】
サーバに設けられたハードウェアは実施態様に応じて変化し得ることが、当業者には認識されよう。図１及び図２に示すハードウェアに加えて又はこれに代えて、他の内部ハードウェアも使用することができる。たとえば、追加のメモリコントローラ、ハードディスク、テープストレージデバイス等を含むことができる。
【００３５】
さらに、当業者には、スタンドアロンコンピューティングデバイス又は分散ネットワーク接続構成でも本発明を実施することができることが理解されよう。たとえば、本発明は、クライアントコンピューティングデバイス、サーバコンピューティングデバイス、パーソナルコンピューティングデバイス等で、単独又は組み合わせで実施することができる。
【００３６】
例示的な実施形態の上記説明は、どの当業者も本発明の製作又は使用することができるように提供されている。本発明は、特定の図示した実施形態に関して説明されてきたが、これらの実施形態に対するさまざまな変形は、当業者には容易に明らかであり、本明細書で定義される包括的な原理は、本発明の趣旨又は範囲から逸脱することなく他の実施形態にも適用することができる。したがって、本実施形態は、すべての点で、制限ではなく例示とみなされることが望まれている。したがって、本発明は、上述した実施形態に限定されるように意図されておらず、本明細書で開示した原理及び新規な機能と一致するより広い範囲を与えられている。
【図面の簡単な説明】
【００３７】
【図１】本発明の一実施形態によるコンピューティングシステムの概略図である。
【図２】本発明の実施形態を実施することができるサーバのブロック図である。
【図３】第１のシリンダグループの従来のＵＮＩＸ（登録商標）ファイルシステムのディスクレイアウトを示すブロック図である。
【図４】本発明の一実施形態による、ｉｎｏｄｅを割り当てる方法を示すフロー図である。
【図５】本発明の一実施形態による、図２に示すサーバのハードディスクにおけるｉｎｏｄｅの割り当てを示すブロック図である。
【図６】本発明によるｉｎｏｄｅマップの概略図である。
【符号の説明】
【００３８】
１００・・・クライアント−サーバコンピューティングシステム
１０２・・・サーバ
１０４・・・クライアント
１０４ａ、１０４ｂ・・・パーソナルコンピューティングデバイス
１０６・・・ネットワーク
１０８・・・ストレージデバイス
１１２ａ、１１２ｂ・・・プロセッサ
１１４・・・システムバス
１１６・・・メモリコントローラ／キャッシュ
１１８・・・メモリ
１２０・・・グラフィックスアダプタ
１２２・・・ディスク
１２４・・・Ｉ／Ｏブリッジ
１２６・・・Ｉ／Ｏバス
１２８ａ〜１２８ｃ・・・ＰＣＩバスブリッジ
１３０ａ〜１３０ｃ・・・ＰＣＩバス
１３２・・・モデム
１３４・・・ネットワークアダプタ
５０２、５０８・・・alloc_map
５０４、５０６、５１０・・・inode_chunk
【図１】
2009064417.tif 000003
【図２】
2009064417.tif 000004
【図３】
2009064417.tif 000005
【図４】
2009064417.tif 000006
【図５】
2009064417.tif 000007
【図６】
2009064417.tif 000008
【外国語明細書】
A Method and a Computer Program for Inode Allocation and De-Allocation
Background of the Invention
Inodes are data structures which are utilised by many file systems to store basic meta-data about a file, directory, or other file system object.  Examples of file systems which utilise inodes include the UNIX File System (UFS), Veritas File System (VxFS) and the EXT2 File System, among others. 
Inodes are pre-allocated and pre-initialized in an inode table during file system creation.  The file system calculates the number of inodes that are to be provided in the inode table by using an algorithm which considers the size of the file system partition and the average file size.  The file system then stores the inodes at a fixed offset in a contiguous block of disk space (i.e. the inode table), which is disparate to the portion of disk space used for storing actual data.  In UNIX file systems, inodes are stored in the inode table in sequential order, to allow the inodes to be fetched directly using the inode number as the offset.  That is, there is a direct mapping of the inode number to the disk block address of the inode (i.e. location of inode in the inode table).  
The number of inodes in the inode table can neither be increased nor decreased once the File System has been created.  That is, the inode table is fixed.  File systems often include applications which are programmed to store many small files which may ultimately utilise all available inodes in the inode table, thereby preventing other applications from storing further files even if there is available disk space.  In the alternative, the file system may pre-allocate too many inodes; resulting in the file system performing unnecessary processing operations during file system creation.  This is particularly the case for file systems having resident applications which store small numbers of large files.
Brief Description of the Drawings
In order that the invention may be more clearly ascertained, embodiments will now be described, by way of example, with reference to the accompanying to drawings, in which; 
Fig. 1 is a schematic view of a computing system according to an embodiment of the present invention.
Fig. 2 is a block diagram of a server, in which embodiments of the present invention may be implemented.
Fig. 3 is a block diagram illustrating a conventional UNIX file system disk layout for a first cylinder group.
Fig. 4 is a flow diagram illustrating a method for allocating inodes, according to an embodiment of the present invention.
Fig. 5 is a block diagram illustrating allocation of inodes on a hard disk of the server shown in Fig. 2, in accordance with an embodiment of the present invention.  
Fig. 6 is a schematic of an inode map, in accordance with the present invention.
Detailed Description of the Embodiments
There will be provided a method and computer program for allocating and de-allocating inodes in a computing file system.
In one embodiment, the method of allocating inodes comprises the steps of determining whether all inodes in a first inode table provided on the computing file system have been initialized and, responsive to determining that all inodes in the first inode table have been initialized, creating a further inode table allocating additional inodes.
In another embodiment, there is provided a computer program comprising at least one instruction which, when implemented on a computer readable medium of a computing system, causes the computing system to implement the inode allocation method steps described above.
In another embodiment, there is provided a method of de-allocating inodes in a computing file system including at least a first and further inode table, comprising the steps of determining whether the further inode tables contains no initialized inodes; and responsive to determining that the further table contains no initialized inodes, deleting the further inode table.
In another embodiment, there is provided a computer program comprising at least one instruction which, when implemented on a computer readable medium of a computing system, causes the computing system to implement the inode de-allocation method steps described above.
In the context of the specification, the phrase "inode table" is to include within its scope any table which can be stored in any suitable disk space and which includes at least one inode which can be either initialized or de-initialized.  
There will also be provided a computing system, such as the client-server computing system 100 illustrated in Fig. 1, which is configured to implement the above-described methods.  In one embodiment, the client-server computing system 100 comprises a server 102 which is connected to clients 104, via a network in the form of the Internet 106.  Clients 104 are in the form of personal computing devices 104a, 104b comprising standard hardware and software for communicating with the server 102. The clients 104 communicate with the server 102 using the Transmission Control Protocol/Internet Protocol (TCP/IP) suite of protocols.  A storage device 108 is also connected to the network 106.
With reference to Fig. 2, there is shown a block diagram of the hardware and software for the server 102, which in accordance with the described embodiment is in the form of a HP-UX rx5670 server, available from the Hewlett Packard Company.  The server 102 runs an operating system in the form of a UNIX operating system 132 with a UNIX stack.  It should be noted that, although in this embodiment the server 102 implements a UNIX operating system 132, other embodiments may include different operating systems such as, for example, the LINUX operating system.  
The UNIX operating system also includes a file system in the form of a Unix File System (UFS).  The UFS is composed of a collection of cylinder groups and includes software for controlling the transfer of data between the network 106 and hard disk 122.  A buffer cache composed of part of memory 118 is used as a buffer for this data transfer. The buffer cache is also arranged to hold contents of disk blocks for the purpose of reducing frequent high latency disk I/Os.
The server 102 further includes a number of processors 112 in the form of quad Intel Itanium 2 processors 112a, 112b (available from the Intel Corporation of The United States of America, http://www.intel.com/) coupled to a system bus 114.  A memory controller/cache 116 is also coupled to the system bus 114 and is arranged to interface the memory 118, which is in the form of double data rate DDR SDRAM.  Also provided is a graphics adapter 120 for handling high speed graphic addressing and an ATA gigabyte hard disk 122 which are connected to an I/O bus bridge 124, by way of an I/O bus 126.  The memory controller 116 and I/O bus bridge may be interconnected, as shown in Fig. 2.
Connected to the I/O bus 126 are PCI bus bridges 128a, 128b, 128c, which provide an interface to devices connected to the server 102 via PCI buses 130a, 130b, 130c.  A modem 132 and network adapter 134 are coupled to PCI bus 130a.  The network adapter 134 is configured to allow the server 102 to exchange data with clients 104 using the TCP/IP protocol.  As will be appreciated by person skilled in the art, additional I/O devices such as a CD-ROM, may also be coupled to the server 102 via I/O busses 130a, 130b, 130c.
As discussed above, the UFS divides the hard disk 122 of the server 102 into multiple cylinder groups.  In a conventional UFS disk layout, each cylinder group is composed of a backup copy of a file system superblock, a group header (which includes statistics, free lists, and other information describing the cylinder group), and an inode table comprising a fixed number of pre-allocated and pre-initialized inodes. The size of the inode table is calculated based on the size of the file partition and the average file size, during file system creation (i.e. when the command mkfs is invoked in the UFS operating system).  A conventional cylinder disk layout is illustrated in Fig. 3.
Embodiments of the present invention utilise a dynamic inode allocation method which allocates additional inodes (typically in blocks, referred to as further or additional inode tables), as required by the file system.   As additional inodes may be allocated after the initial file system creation, the number of inodes initially allocated may be significantly less than required by conventional file systems.  The methodology is also capable of de-allocating inodes where the file system no longer has a need for the number of inodes currently allocated.
With reference to the flow diagram of Fig. 4, an inode allocation method for a computing file system including a first inode table, will now be described in accordance with an embodiment of the present invention.  In the described embodiment, the first inode table is created at the time of creating the file system and inodes in the first inode table are initialized as required by the resident applications.  At step 402, a determination is made as to whether all inodes in the first inode table have been initialized.  If, at step 404, it is determined that the number of inodes required by the file system exceeds the capacity of the first inode table (i.e. all inodes in the first inode table have been initialized), a further inode table is created allocating additional inodes.  It will readily be understood that any number of further/additional inode tables can be created in this manner and stored any suitable disk location, dependent only on the amount of available disk space, as will be described in more detail in subsequent paragraphs.
In order to allow resident applications to locate a desired inode, at step 406, a data structure in the form of an inode map (hereafter termed "alloc_map") is created.  The alloc_map is effectively an array of disk block addresses which point to successive inode tables (hereafter "inode_chunks").  Fig. 6 illustrates a typical structure for an alloc_map.  As shown, the nth entry in the alloc_map points to an inode_chunk which contains the inodes numbered from (n*inodechunksize) to (((n+1) *inodechunksize)-1).  However, using just one map would restrict the inodes to (allocmapsize) *(inodechunksize).  As such further alloc_maps may be created, where required, so as to reference all allocated inodes. The disk space required for the extended alloc_maps or inode_chunks need not be pre-reserved by the file system.
Fig. 5 illustrates the above-described method in more detail.  For simplicity, the methodology described with reference to Fig. 5 provides that each alloc_map is arranged to point to the disk address of four inode_chunks. During file system creation, only the first alloc_map 502 and the first inode_chunk 504 are allocated. As illustrated, the first entry in alloc_map 502 points to the first inode_chunk 504. When the number of inodes exceeds the capacity of the first inode_chunk 504, a further inode_chunk 506 is allocated. Similarly, when the capacity of the alloc_map 502 is exceeded (in this case when a further inode-chunk 510 has been allocated), a new alloc_map 508 is allocated and linked to the previous alloc_map 502.
An example of pseudo computer programmable code which may be used to retrieve inodes using the methodology outlined above is provided below. 
IGET (inode_number) : returns inode
{
inode_chunk_number = inode_number / chunksize
alloc_map_number = inode_chunk_number / allocmapsize
if (alloc_map corresponding to alloc_map_number does not exist)
{
* Allocate a new alloc_map of size allocmapsize
* Initialize the entries of alloc_map properly
* Link this alloc_map to pervious and next alloc_maps
}
if (inode_chunk corresponding to inode_chunk_number does not exist)
{
* Allocate an inode_chunk of size chunksize
* Initialize the (inode_chunk_number % allocmapsize)th
entry in the alloc_map to the starting address of this
inode_chunk
}
* Get the starting address of the inode_chunk from the alloc_map (at
the offset ( inode_chunk_number % allocmapsize )
* Fetch the required inode from the inode_chunk at the offset
(inode_number % chunksize) and return this inode.
}
Equation 1 below is used to determine the total time for fetching an inode using the above-described method.  As will be shown, this data can then be utilised by the file system to establish the most appropriate inode_chunk and alloc_map size.
T = Tca + Tci + Tsa + Taa + Tia + Tsic + Tai + Tii + Tsi    (Equation 1)
where:
Tca =    Time to compute the alloc_map number
Tci=     Time to compute the inode_chunk number
Tsa=    Time to search and fetch the required alloc_map
Taa=    Time to allocate a new alloc_map
Tia=    Time to initialize the alloc_map
Tsic=     Time to search and fetch the required inode_map
Tai=    Time to allocate a new inode_chunk
Tii=     Time to initialize the inode_chunk
Tsi=    Time to search and fetch the required inode from the inode_chunk
In Equation 1, Tca and Tci are both constant times (i.e. no disk access is required) and can therefore be represented by Kca and Kci, respectively. Also, the allocation and initialization of a new disk block (for alloc_map and inode_chunk) needs only one disk access each for updating the super block (which can also be avoided by modifying only the "in memory" copy of the super block). Therefore, these times (i.e. Taa, Tia, Tai and Tii) can be represented by constants Kaa, Kia, Kai and Kii, respectively. The step of searching for alloc_map is directly proportional to the number of alloc_maps. If n is the number of alloc_maps in the file system, then the process of searching for alloc_map needs n disk accesses. That is, Tsa = n*Ksa, where Ksa is a constant representing the time required to fetch one alloc_map. Then Tsic and Tsi are again constant time operations (as shown in the algorithm). Let these be represented by Ksic and Ksi respectively.
Therefore, the total time required by the algorithm is:
T     = (Tca + Tci)+ (Tsic + Tsi) +( Taa + Tia + Tai+ Tii) + Tsa 
= K + n*Ksa (Sum of all constants are replaced by K for simplicity)
As such, the time complexity of this algorithm is:
O(T)     = O( K )+ O(n*Ksa )
Approx= O(n) (Since K and Ksa are constants)
That is, the performance overhead for the algorithm described herein is a linear equation with respect to the number of alloc_maps. Though performance can be poor for very high values of n (>100), the sizes of both alloc_map and inode_chunk (which are set at file system creation time) are calculated as a function of the file system size to avoid an impact on the performance of the algorithm. In general, the number of alloc_maps (n) need not exceed four. 
For example, consider a file system of size 1Tera Byte, alloc_map size as 1Mega Byte and inode_chunk size as 512 kilobyte. Assuming 8 byte addresses, a single alloc_map can hold 217 inode_chunk addresses. Even if an inode_chunk can hold just 512 inodes, a single alloc_map is sufficient to handle (217) * (29) = (226) inodes. So, using four alloc_maps (228) provides 268,435,456 inodes, which is large enough for most practical scenarios.
Although the embodiment described herein described a method for the allocation of inode tables, it is noted that the method is equally capable of de-allocating (or deleting) inodes and inode tables in a computing file system which includes multiple inode tables (i.e. a first inode table and further or additional inode tables).  When a file in the file system is deleted, the corresponding inode is de-initialized by an inode de-initialization code, to thereby allow another file to use the inode.  If the inode de-initializing code determines that the inode which is being de-initialized is the last remaining inode in the associated inode table, the code path de-allocates (i.e. deletes) the entire inode table and updates the associated inode map accordingly.
Embodiments of the allocation and de-allocation methods may be implemented by a computer program (in either hardware, software or a combination of the two) comprising instructions which, when implemented on a computer readable medium of a computing system, causes the computing system to implement the method steps described above.
Although not required, the computer program may be implemented via an application programming interface (API), for use by a developer, and can be implemented in code within another software application. Generally, as software applications include routines, programs, objects, components, and data files that perform or assist in the performance of particular functions, it will be understood that a software application may be distributed across a number of routines, objects and components, but achieve the same functionality as the embodiments and the broader invention claimed herein. Such variations and modifications would be within the purview of those skilled in the art.
Those of ordinary skill will appreciate that the hardware provided in the server may vary depending on the implementation.  Other internal hardware may be used in addition to, or in place of, the hardware depicted in Figs 1 & 2.  For example, included may be additional memory controllers, hard disks, tape storage devices, etc.
Furthermore, it will be understood by persons skilled in the art that the invention may be implemented in a stand alone computing device or in a distributed, networked configuration.  For example, the present invention may be implemented solely or in combination in a client computing device, server computing device, personal computing device, etc. 
The foregoing description of the exemplary embodiments is provided to enable any person skilled in the art to make or use the present invention.  While the invention has been described with respect to particular illustrated embodiments, various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the invention.  It is therefore desired that the present embodiments be considered in all respects as illustrative and not restrictive.  Accordingly, the present invention is not intended to be limited to the embodiments described above but is accorded the wider scope consistent with the principles and novel features disclosed herein.  
Claims:
1.    A method of allocating inodes in a computing file system including a first inode table, the method comprising the steps of:
determining whether all inodes in the first inode table have been initialized; and
responsive to determining that all inodes in the first inode table have been initialized, creating a further inode table allocating additional inodes.
2.    A method of allocating inodes in accordance with Claim 1, comprising the further step of creating at least one additional inode table when all inodes in the further inode table have been initialized.
3.    A method of allocating inodes in accordance with Claim 1, comprising the further step of providing one or more inode map(s), the inode map(s) pointing to a disk block address of the inode table including a selected allocated inode.
4.    A method of allocating inodes in accordance with Claim 3, wherein the number of inodes in each inode table is a function of a total amount of disk space and the number of inode tables addresses to be referenced in each inode map.
5.    A method of allocating inodes in accordance with Claim 4, comprising the further step of determining the number of inodes during file system creation.
6.    A method of de-allocating inodes in a computing file system including at least a first and further inode table, comprising the steps of:
determining whether the further inode tables contains no initialized inodes; and 
responsive to determining that the further table contains no initialized inodes, deleting the further inode table.
7.    A method of de-allocating inodes in accordance with Claim 6, comprising the further step of deleting a reference to the further inode table in an inode map associated with the further inode table.
8.    A method of de-allocating inodes in accordance with Claim 7, comprising the further step of:
deleting the inode map associated with the further table, in response to determining that the further table is the only table referenced by the inode map.
9.    A computer program for allocating inodes in a computer file system including a first inode table, the program comprising at least one instruction which, when implemented on a computer readable medium of a computing system, causes the computing system to implement the steps of:
determining whether all inodes in the first inode table have been initialized; and
responsive to determining that all inodes in the first inode table have been initialized, creating a further inode table providing additional inodes.
10.    A computer program in accordance with Claim 9, arranged to implement the further step of creating at least one additional inode table when all inodes in the further inode table have been initialized.
11.    A computer program in accordance with Claim 9, arranged to implement the further step of providing one or more inode map(s), the inode map(s) pointing to a disk block address of the inode table including a selected allocated inode.
12.    A method of allocating inodes in accordance with Claim 11, wherein the number of inodes in each inode table is a function of a total amount of disk space and the number of inode tables addresses to be referenced in each inode map.
13.    A computer program in accordance with Claim 12, arranged to implement the further step of determining the number of inodes during file system creation.
14.    A computer program for de-allocating inodes in a computer file system including at least a first and further inode table, the program comprising at least one instruction which, when implemented on a computer readable medium of a computing system, causes the computing system to implement the steps of:
determining whether the further inode table contains no initialized inodes; and 
responsive to determining that the further inode table contains no initialized inodes, deleting the further inode table.
15.    A computer program in accordance with claim 14, arranged to implement the further step of deleting a reference to the further inode table in an inode map associated with the further inode table.
16.    A computer program in accordance with claim 15, arranged to implement the further step of:
deleting the inode map associated with the further table, in response to determining that the further table is the only table referenced by the inode map.
17.    A computer readable medium providing a computer program product in accordance with Claim 9. 
18.    A computer readable medium providing a computer program product in accordance with Claim 14.
Abstract of the Disclosure
The present disclosure relates to a method and computer program for allocating inodes in a computing file system.  The method, in one embodiment, includes determining whether all inodes in a first inode table have been initialized.  Responsive to determining that all inodes in the first inode table have been initialized, a further inode table is created allocating additional inodes.
(Fig. 4)
2009064417.tif 000009
2009064417.tif 000010
2009064417.tif 000011
2009064417.tif 000012
2009064417.tif 000013
2009064417.tif 000014