Michael Hicks, Scott Nettles, "Dynamic Software Updating", ACM TOPLS 2003(2)

論文

これの続き。

動的パッチを実装する

動的パッチを実装する際に、基本的には二つの方法がある。

  • 古いコードを動かしているコンピュータとは別のコンピュータを用意し、新しいコードをコンパイルして、そちらで稼動させる。そして、古い方にシグナルを送り、状態を送ってもらう。その状態を、state transformer関数を用いて変換し、可動を開始する。このアプローチを、state transfer-basedアップデートと呼ぶ。
  • もう一つの方法は、既存のプログラムに新しいコードを動的にリンクし、ローカルに状態を変換し、新しいコードへ移行すると言うものである。この方法を、dynamic linking-basedアップデートと呼ぶ。

state transfer-basedの方法は、Guptaらによって実装されている。本稿では、以下のような理由からdynamic linking-basedアップデートを採用する。

  • 古いコードと新しいコードが共存できない。
  • ほんの少しのアップデートの場合でも、全てのプログラムを移行しないといけないため、コストがかかる。
  • 状態を変換するのは、思いのほか難しい。プログラムカウンタやヒープ、スタックなども扱う必要があるからである。実際に、Guptaは、スカラーであるグローバル変数のアップデートしか許していない。この点を解決するには、Rankumar and Strumpen 1997が参考になるかもしれない。
  • ファイル記述子やプロセスの親子関係などのようなプログラムの状態は、OSのカーネル内に記録されるため、アップデート後のプロセスに渡すのが難しい。
コードとデータのアップデート

これにも、二つの方法が考えられる。

  • アップデートしたい関数やデータの参照先を直接書き換える。(code relinkingと呼ぶ)
  • 関数やデータの参照を、必ずindirection tableというテーブルを通して行うようにすると、そのテーブルの目的の関数またはデータの参照先を書き換えるだけで、全ての関数・データの参照を書き換えることが出来る。(reference indirectionと呼ぶ)

(これらの手法は、本論文の１３ページのFigure 7を見るとすぐわかると思います。)
本稿では、以下のような理由からcode relinkingを採用する。

  • テーブルを参照する方式だと、オーバーヘッドが気になる。
  • code relinkingの方が実装しやすい。

二つの方式のハイブリッドを使うといいかもしれない。

型定義のアップデート(ここ良くわかってないかも）

二つの選択肢が考えられる。

  • 型定義を置き換える方法。この方法では、型チェックのコンテクストを書き換え、型チェックする。この方法を、replacementと呼ぶ。
  • 型定義の名前付けをしなおす方法。この方法では、古い型定義とは別の名前で新しい型を定義し、それぞれの型を持つ値は共存する。そして、state transformer関数やスタブ関数をアップデート時などに使って新しい型の値を得る。この方法を、renamingと呼ぶ。

これらの方法については、本論文15ページのFigure8を参照してください。

  • replacement
    • 利点：使いやすい。柔軟性がある。
    • 欠点：型の古いバージョンが失われてしまうため、全ての古い型が新しい型に変換できると言うことを保証しなければいけない。
  • renaming
    • 利点：古いバージョンと新しいバージョンの型定義が保持されているため、アップデートのタイミングが自由である。
    • 欠点：プログラマが、state transformer関数やスタブ関数などで古い型の値から新しい型の値への変換を記述しないといけない。

ここでは、実装の簡単のためrenamingを採用している。

プロトタイプの実装

本論文での動的アップデートのためのフレームワークでは、TAL(Typed Assembly Language)をターゲットにしている。型付きのアセンブリ言語を用いることによって、型チェックで示すことのできる安全性は保証することが出来る。この論文で使われているPopcornと言う言語はCに似た言語で、PopcornからTALをはくためのコンパイラと、TALの型チェックを行う検証器がIntel IA32用に実装されている(TALx86という)。
TALでは、type safeな動的リンカが用意されていて、その中心的な役割を果たしているのが、loadというプリミティブです。この動的リンカではロードしたいファイルは、外部への参照が全てglobal offset table(GOT)と呼ばれる表を介して参照するようにコンパイルされます。(Hicks et al. 2000参照)。(この辺りの話に関しては、日本語で良さそうなpptが落ちていたのでそちらも参照してみてください)。そして、現在動いているプログラムのexport定義とGOT照らし合わせて、参照関係を解決します。動いているプログラムのexportの定義は、dynamic symbol tableという表で管理されていて、シンボルの名前からそのアドレスへの写像を表しているハッシュテーブルのリンクリストとなっています。
動的アップデートを解決するには、この枠組みを以下のように少し変更します。

  1. 静的リンク、動的リンク、どちらのリンク方法をとるにしても、外部への参照をGOTを介して行うようにコンパイルする。
  2. A用のパッチをロードするとき、dynamic symbol tableに保存する新しいハッシュテーブルを作成します。リンク中や、state transformation中にエラーが起きた場合は、この新しいハッシュテーブルを捨てる事で、状態を元に戻します。そして、状態を変換する処理が完了したらば、既存のプログラムのコードがrelinkされる。そして、最後に古いAのハッシュテーブルはdynamic symbol tableから削除されます。複数のパッチを同時にあてる場合は、相互再帰的な参照が存在するかもしれないので、複数パスのリンクが必要となります(Hicks 2001を参照)。

こういった機能を実現するために、動的リンカを以下のように変更しました。

  • static変数を扱えるようにするため、名前の衝突を避けるために、ローカル変数にfilename::Local::と付けることにする。
  • リンクの順番をカスタマイズできるようにする。これは、state transformer関数の中で古い変数と新しい変数の両方を参照する可能性があるので、アップデートする前の表の中身を見る必要があるためです。
  • プログラム中のシンボルを、dynamic symbol tableの異なる名前へ割り振ることが可能です。こうすることで、スタブ関数で全く同じ名前では無い関数に置き換えることが出来ます。
  • Aというモジュールにパッチがロードされた後、古いAが使われている場合は、そちらへrelinkする必要がある。relink中にルックアップをすると、異なった型の関数を見つけてしまう可能性があり、そういった場合には、二次的に古いハッシュテーブルを検索して、古いバージョンを探せるようにする必要がある。
  • relinkが完了したら、古いハッシュテーブルはGCされることが出来るようになる。しかし、以降のアップデートで再度古いハッシュテーブルが必要になる可能性があるため、厳密には正しくない。こういった場合に効率よく対処するためには、weak pointerを使って、dynamic symbol tableで保持すると良い。weak pointerとは、他のweakでないポインタから参照されていない場合は、GCによって回収されても良いというような参照のことである。

パッチの生成

この論文の成果として、パッチをほぼ自動的に生成することができるというものがある。このパッチ生成器は、Garlan et al. 1986のtransformGenというデータベーススキーマの考え方に似ている。

自動パッチ生成

パッチ生成器は、入力として

  • 古いファイル
  • 新しいファイル
  • 現在の型定義
  • 古い型定義
  • 型変換ファイル

を受け取り、出力として

  • インターフェースコードファイル
  • パッチファイル
  • 現在の型定義
  • 型変換ファイル

を得る。
パッチ生成は、識別と生成という2段階に分ける事が出来ます。識別段階では、古いファイルと新しいファイルを入力として受け取り、他の入力ファイルから変更される型も入力として使います。その後古いファイルと新しいファイルがパースされ型チェックが行われ、新しいファイルのそれぞれの定義に対して、古いファイルから対応する名前を検索します。型定義の場合は、定義のボディーが比較されます。その場合、比較したもの同士が異なったら、変更される型の集合に追加されます。値の宣言の場合、ボディーが比較されます。識別フェーズでは、以下の情報を得る事が出来ます。

  • 変更される関数
  • 変更されるが型は変わらない関数
  • 変更されないデータ宣言
  • 変更されるデータ宣言
  • 変更されない型
  • 変更される型

さらに、パッチ生成器によって生成されるファイルについて説明します。

  • インターフェースコードファイル。このファイルでは、state transformation関数Sと、スタブ関数を含んでいます。Sを構築するには、以下のようにします。変更されていないグローバル変数は単純にコピーする。値の型が変更されている場合は、コピーの途中で型が変換される必要があります。型定義が変更されている場合は、型変換関数を用いて変換します。スタブ関数を構築するには、二通り考えられる。単純なものは、生成器が古い型を持つボディーを持ち、例外を投げると言うものです。もう一つは、適切に古い型の値を受けとり、新しい型の値を生成する関数を自動的に呼び出すものです。
  • 型名写像ファイル。識別フェーズ中に、どの型定義が変更されるかと言う事は、監視されている。そして、変更される型に関しては、MD5を使って新しい名前を付けます。そして、古い型から新しい型への写像は、型名写像ファイルに保存されます。
  • 型変換ファイル。古い型の値から新しい型の値への変換とその逆が型変換ファイルに記述されます。これらの関数は、上のインターフェースコードファイルで使用されます。

以上のような、自動処理で生成することの出来ないstate transformer関数やスタブ関数は、プログラマが記述する必要があります。
ここで例として、以上の処理を



old version old_foo.pop:
typedef struct {

   int a; int b;

} *t;

t someTs[];

int f (t T) {

   return T.a + T.b;

}


new version new_foo.pop:
typedef struct {

   itn a; int b; int c;

} *t;

t someTs[];

int f (t T) {

   return T.a + T.b;

}
という二つのファイルに関して行うとどういう結果が得られるかを、下に示します。



new_foo.patch:
implementation: new_foo.pop

interface: new_foo_patch.pop

renaming:

   New::t=MD5(

      typedef struct {

         int a; int b; int c;

      } *t)


TYPENAME_MAP:
New::t=MD5(

   typedef struct {

      int a; int b; int c;

   } *t)


new_foo_patch.pop:
#include "core.h"

typedef struct {

   int a; int b;

} *t;

extern t someTs[];

extern New::t t__old2new(t);

static void S(){

   int idx__0;

   for(idx__0 = 0; idx__0 < size(someTs); ++idx__0)

      New::someTs[idx__0] = t__old2new(someTs[idx__0]);

}

prefix Stub{

   int f(t v0){

      raise (new Core::InvalidArg("Stub?f (int (New::t))"));

   }

}


convert_patch.pop:
typedef struct{

   int a; int b;

} *t;

typedef struct{

   int a; int b; int c;

} *New::t;

New::t t__old2new(t from){

   if(from == NULL)

      return NULL;

   else{

      New::t to = new New::t{b=from.b, a=from.a, c=0};

      return(to);

   }

}

t t__new2old(New::t from){

   if(from == NULL)

      return NULL;

   else{

      t to = new t{b=from.b, a=from.a};

      return(to);

   }

}

いつパッチをあてるか

(後で書く)

実用例

本論文で構築した動的アップデートシステムを、実際にウェブサーバーを実装して使ってみた例が載っていましたが、ここでは省略します。その次に性能評価の議論もされています。