タグ付きポインタ

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

コンピュータサイエンスではタグ付きポインタは、間接ビット参照カウントなどの追加データが関連付けられたポインタ(具体的にはメモリアドレス)です。この追加データは、多くの場合、ポインタに「折りたたまれ」ます。つまり、メモリアドレス指定の特定のプロパティを利用して、アドレスを表すデータにインラインで格納されます。この名前は、各単語の重要性を示すためにハードウェアレベルでビットを予約した「タグ付きアーキテクチャ」システムに由来しています。追加のデータは「タグ」または「タグ」と呼ばれますが、厳密に言えば「タグ」はタイプを指定するデータを指します。他のデータではありません。ただし、「タグ付きポインタ」の使用法はどこにでもあります。

タグをポインタに折りたたむ

タグをポインタに折りたたむには、さまざまな手法があります。[1] [信頼できない情報源?]

ほとんどのアーキテクチャはバイトアドレス可能です(アドレス可能な最小単位はバイトです)が、特定のタイプのデータは、多くの場合、データのサイズに合わせて調整されます。多くの場合、ワードまたはその倍数です。この不一致により、ポインタの最下位ビットのいくつかが未使用のままになります。これは、ポインタを使用するコードがアクセスする前にこれらのビットをマスクする限り、タグに使用できます。ほとんどの場合、ビットフィールド(各ビットは個別のタグ)として使用できます。メモリー。たとえば、32ビットアーキテクチャ(アドレスとワードサイズの両方)では、ワードは32ビット= 4バイトであるため、ワード整列アドレスは常に4の倍数であるため、00で終わり、最後の2ビットが使用可能になります。にいる間64ビットアーキテクチャでは、ワードは64ビット= 8バイトであるため、ワードアラインされたアドレスは000で終わり、最後の3ビットが使用可能になります。データがワードサイズの倍数で整列されている場合は、さらにビットを使用できます。ワードアドレス指定可能なアーキテクチャの場合、アラインメントとアドレッシングの間に不一致がないため、ワードアラインされたデータは使用可能なビットを残しませんが、ワードサイズの倍数でアラインされたデータはそうします。

逆に、一部のオペレーティングシステムでは、仮想アドレスがアーキテクチャ全体の幅よりも狭いため、タグに使用できる最上位ビットが残ります。これは、アドレスが整列されている場合、以前の手法と組み合わせることができます。これは特に64ビットアーキテクチャの場合に当てはまります。64ビットのアドレス空間は、最大規模のアプリケーションを除くすべてのアプリケーションのデータ要件をはるかに上回っているため、多くの実用的な64ビットプロセッサのアドレスは狭くなっています。仮想アドレス幅は物理アドレス幅よりも狭い場合があり、物理アドレス幅はアーキテクチャ幅よりも狭い場合があることに注意してください。ユーザースペースでのポインタのタグ付け用、オペレーティングシステムによって提供される(メモリ管理ユニットによって提供される)仮想アドレス空間は、関連する幅です。実際、一部のプロセッサは、プロセッサレベルでのこのようなタグ付きポインタの使用を特に禁止しています。特にx86-64では、オペレーティングシステムによる正規形アドレスの使用が必要であり、最上位ビットはすべて0またはすべて1です。

最後に、最新のオペレーティングシステムのほとんどの仮想メモリシステムは、アドレス0の周りの論理メモリのブロックを使用不可として予約しています。これは、たとえば、0へのポインターが有効なポインターになることはなく、特別なnullポインター値として使用できることを意味します。前述の手法とは異なり、これは単一の特別なポインター値のみを許可し、一般にポインターの追加データは許可しません。

商用プラットフォームでのタグ付きポインターのハードウェアサポートの最も初期の例の1つは、IBM System/38でした。[2] IBMは後に、System /38プラットフォームの進化形であるIBMiオペレーティング・システムをサポートするために、 PowerPCアーキテクチャーにタグ付きポインターのサポートを追加しました。[3]

タグ付きポインターの使用の重要な例は、特にiPhone5Sで使用されるARM64上のiOS7でのObjective-Cランタイムです。iOS 7では、仮想アドレスには33ビットのアドレス情報しか含まれていませんが、長さは64ビットで、タグ用に31ビットが残っています。Objective-Cクラスポインタは8バイトで整列され、追加の3ビットのアドレス空間を解放します。タグフィールドは、参照カウントの格納やオブジェクトにデストラクタがあるかどうかなど、さまざまな目的で使用されます[4] [5]

MacOSの初期のバージョンでは、Handlesと呼ばれるタグ付きアドレスを使用してデータオブジェクトへの参照を格納していました。アドレスの上位ビットは、データオブジェクトがロックされているか、パージ可能であるか、またはリソースファイルから発信されているかをそれぞれ示しています。これにより、システム7でMacOSアドレス指定が24ビットから32ビットに進んだときに互換性の問題が発生しました。[6]

ヌル対整列ポインタ

ヌルポインタを表すためにゼロを使用することは非常に一般的であり、多くのプログラミング言語(Adaなど)はこの動作に明示的に依存しています。理論的には、オペレーティングシステムで予約された論理メモリのブロック内の他の値を使用して、nullポインタ以外の条件にタグを付けることができますが、これらの使用はまれであるように見えますソフトウェア設計では、nullとは異なる特別なポインタ値(特定のデータ構造の番兵など)が必要な場合、プログラマーが明示的に指定する必要があることが一般的に認められています。

ポインターの配置を利用すると、ポインターがポイントされるデータのタイプ、アクセスされる条件、またはポインターの使用に関する他の同様の情報でタグ付けできるため、nullポインター/センチネルよりも柔軟性が高くなります。この情報は、すべての有効なポインターとともに提供できます。対照的に、nullポインター/センチネルは、有効なポインターとは異なる有限数のタグ付き値のみを提供します。

タグ付きアーキテクチャでは、メモリのすべてのワードのビット数がタグとして機能するように予約されていますLispマシンなどのタグ付きアーキテクチャは、多くの場合、タグ付きポインタを解釈および処理するためのハードウェアサポートを備えています。

GNU libc malloc()は、32ビットプラットフォーム用に8バイトアライメントのメモリアドレスを提供し、64ビットプラットフォーム用に16バイトアライメントを提供します。[7]を使用すると、より大きなアライメント値を取得できますposix_memalign()[8]

例1

次のCコードでは、ゼロの値はnullポインターを示すために使用されます。

voidoptional_return_a_value int * optional_return_value_pointer { _    
  / * ... * /
  int value_to_return = 1 ;   

  / * NULL以外ですか?(NULL、論理false、およびゼロはCで同等に比較されることに注意してください)* /
  if optional_return_value_pointer  
    / *その場合は、それを使用して呼び出し元の関数に値を渡します* /
    * optional_return_value_pointer = value_to_return ;  

  / *それ以外の場合、ポインタは逆参照されません* /
}

例2

ここで、プログラマーはグローバル変数を提供し、そのアドレスはセンチネルとして使用されます。

#define SENTINEL&sentinel_s

node_tsentinel_s ; _ 

void do_something_to_a_node node_t * p {     
  if NULL == p    
    /*何かをする*/
  else if SENTINEL == p     
    /*何か他のことをする*/
  そうしないと
    /*pをノードへの有効なポインタとして扱います*/
}

例3

table_entry常に16バイトの境界に揃えられているデータ構造があると仮定します。つまり、テーブルエントリのアドレスの最下位4ビットは常に0 2 4 = 16)です。 これらの4ビットを使用して、テーブルエントリに追加情報をマークすることができます。たとえば、ビット0は読み取り専用を意味し、ビット1はダーティ(テーブルエントリを更新する必要がある)を意味する場合があります。

ポインタが16ビット値の場合、次のようになります。

  • 0x3421table_entryatアドレスへの読み取り専用ポインタです0x3420
  • 0xf472ダーティtable_entryアットアドレスへのポインタです0xf470

利点

タグ付きポインタの主な利点は、個別のタグフィールドとともにポインタよりも占有するスペースが少ないことです。これは、ポインタが関数からの戻り値である場合に特に重要になる可能性がありますこれは、ポインタの大きなテーブルでも重要になる可能性があります。

より微妙な利点は、ポインターと同じ場所にタグを格納することにより、外部同期メカニズムなしでポインターとそのタグの両方を更新する操作のアトミック性を保証できることが多いことです。これは、特にオペレーティングシステムで、非常に大きなパフォーマンスの向上になる可能性があります。

短所

タグ付きポインタには、程度は低いものの、xorリンクリストと同じ問題がいくつかあります。たとえば、すべてのデバッガーがタグ付きポインターを正しく追跡できるわけではありません。ただし、これは、タグ付きポインターを念頭に置いて設計されたデバッガーの場合は問題になりません。

nullポインターを表すためにゼロを使用しても、これらの欠点はありません。これは広く普及しており、ほとんどのプログラミング言語はゼロを特別なnull値として扱い、その堅牢性を徹底的に証明しています。例外は、ゼロがC ++の過負荷解決に関与する方法です。ここで、ゼロはポインターではなく整数として扱われます。このため、整数のゼロよりも特別な値nullptrが優先されます。ただし、タグ付きポインターでは、通常、ヌルポインターを表すためにゼロは使用されません。

参照

  1. ^ 金曜日のQ&A 2012-07-27:タグ付きポインタを作成しましょう、MikeAsh
  2. ^ Levy、Henry M.(1984)。「IBMSystem/38」 (PDF)機能ベースのコンピュータシステムデジタルプレス。ISBN 0-932376-22-3
  3. ^ フランクG.ソルティス(1997)。AS / 400、第2版の内部デュークプレス。ISBN 978-1882419661
  4. ^ 金曜日のQ&A 2013-09-27:ARM64 and You、Mike Ash
  5. ^ [objc Explain]:非ポインタisa
  6. ^ Bricknell、KJ Macintosh C:MacOSをCでプログラミングするための趣味のガイド
  7. ^ 「Mallocの例」GNUCライブラリ2018年9月5日取得
  8. ^ posix_memalign(3)  –  Linuxプログラマーマニュアル–ライブラリ関数