ルーティングアルゴリズムの改良がイマイチだった

WebRTCのやTCPのように、コネクション型の通信経路を使う場合、特定のノードに接続が集中すると、そのノードのリソースが不足したり、負荷が上がってしまう。例えば、macOS sierraではユーザがopenできるディスクリプタの数は256に制限されているため、1ノードに64コネクションも接続すると25%も圧迫することになる。そのため、各ノードへの接続は可能な限り分散することが望ましいと考える。※WebRTCの通信はUDP上にSCTPを実装しているため、TCPほどディスクリプタを消費しないと思うが、経路情報などを個別に持つためメモリや計算負荷はTCPより高くなるのでは?という考えからも、接続は分散したい。

新しいルーティングアルゴリズムを実装してみたものの、ノードの多い・少ない、通信が偏っているか・分散しているかによって、接続が集中してしまうことがわかった。ノードが多く通信が偏っていないようなシミュレーション環境であれば、こうはならなかったのだろうが、自分は実用可能なプログラムを作りたいので、これではいただけない。

シミュレーションや計算で正しいと思われていたアルゴリズムを実装しても、現実の制約などから生じた微妙な差により、シミュレーション通りの動きにならないことを体感。(と言って良いものか、単純に考えが浅いのかもしれない)

収穫は、コネクション型通信を利用したノードが等価なルーティングアルゴリズムにおいて、通信経路の確立は互いに合意がなければならない(片方の合意が無ければ、切断してしまう)と考えていたが、ある一定のルールにより合意がなくとも経路の確立を決定できそうなことかな。

f:id:llamerad-jp:20171013062740p:plain

Xcodeの静的解析ツールに、メモリリークの可能性を指摘されたが釈然としない

経緯

本当はパフォーマンス測定ツールを使って、プログラムが想定外に重い処理を行っていないか、確認したかった。 とりあえず、「Analyze」を起動したら、「Potential memory leak」と言われてビクビク検証している。

f:id:llamerad-jp:20171011063104p:plain

プログラム

分散処理インフラのpicojsonを使っている部分が指摘された。問題を切り分けるため、同様の処理を以下のように切り出した。Analyzeでは同様の警告がでることを確認済み。

#include <string>
#include "picojson.h"

int main(int argc, char* argv[]) {
  std::vector<uint8_t> js_buf;
  std::string js("{}");
  js_buf.resize(js.size());
  memcpy(js_buf.data(), js.c_str(), js.size());

  for (int i = 0; i < 10; i++) {
    picojson::value v;
    std::string err;
    picojson::parse(v, js_buf.begin(), js_buf.end(), &err);
    if (!err.empty()) {
      std::cout << err << std::endl;
      return 0;
    }
  }
  return 0;
}

指摘内容

f:id:llamerad-jp:20171011063506p:plain

かなり細かく指摘される。画像のように、どのメソッドの、どの条件が〜という内容まででる。

メモリリークするのか?

コピーコンストラクタで確保した領域が、開放されない可能性がある?と言いたげだが、デストラクタで開放されている。コピーオペレータでswapを使っているが問題ないように読める。試しにvalgrindを使い、動的に検証するも、やはりリークは起きなかった。 プリプロセッサの展開がうまく解析できない(ような初歩的なことは無いと思いつつ)のかと思い、一応手動で展開したものの、状況は変わらず。 コンストラクタでnewを呼び出すと、メモリ確保の失敗時にstd::bad_alloc例外が発生して、その場合デストラクタが実行されず、リークの原因になりうる。しかし、今回に限ればnewは1度しか呼ばれないため、例外が発生してデストラクタが呼ばれなくとも、そもそも確保に失敗しているためリークは発生しない…はず。 picojsonのデータはunionで格納されており、途中で中の型を記録しているtype_変数を書き換えた場合、正常なdeleteが呼ばれず、メモリリークする可能性があるので、それを指摘したかったのか?と思い、以下のコードをAnalyzerにかけるも何も言われない。解せぬ…。

#include <memory>
#include <string>
#include "picojson.h"

class A {
 public:
  union U {
    int* i;
    char* c;
  };
  bool is_int;
  U u;

  A(bool is_int_) : is_int(is_int_) {
    if (is_int) {
      u.i = new int;
    } else {
      u.c = new char;
    }
  }

  virtual ~A() {
    if (is_int) {
      delete u.i;
    } else {
      delete u.c;
    }
  }
};

int main(int argc, char* argv[]) {
  A a(true);
  bool t = a.is_str;
  a.is_str = true;
  a.is_str = t;

  return 0;
}

もう一度見直す

そもそも、コピーコンストラクタやコピーオペレータ単体で使って再現する様なものではないらしい。試しに以下のコードでは警告が出ない。

#include <iostream>
#include <string>
#include "picojson.h"

int main(int argc, char* argv[]) {
  picojson::value v1;
  picojson::value v2(v1);
  v1 = v2;

  std::cout << v1.serialize() << std::endl;
  std::cout << v2.serialize() << std::endl;

  return 0;
}

実はパース処理の別の場所かもしれないと考え、玉ねぎの皮むきのごとく、1枚1枚関数を剥いて行こうとし、偶然以下のようにしたら警告が出なかった。差分は変数vとerrがforの中にあるか、外にあるかだけ。どちらもスタック変数であり、parse関数からすれば、状態は変わらないはず。forの中に変数がある場合、スコープが1ループごとに作る→開放されるので、vとerrのコンストラクタ、デストラクタの呼ばれる回数などは違うが、それによりメモリリークの有無が変化するとは考えにくい。釈然としないまま保留。どなたかご存知でしたら教えてください。(パフォーマンスの確認をしないとだし)

#include <string>
#include "picojson.h"

int main(int argc, char* argv[]) {
  std::vector<uint8_t> js_buf;
  std::string js("{}");
  js_buf.resize(js.size());
  memcpy(js_buf.data(), js.c_str(), js.size());

  picojson::value v;
  std::string err;

  for (int i = 0; i < 10; i++) {
    picojson::parse(v, js_buf.begin(), js_buf.end(), &err);
    if (!err.empty()) {
      std::cout << err << std::endl;
      return 0;
    }
  }
  return 0;
}

ルーティングアルゴリズムの動きが想定と違う。

何度か動かしているうちに、近隣との接続時の動作が想定と異なる気が。確認のため、10%の割合でランダムにノードをkillするようにしたら、その情報がうまく更新されていない動きをするようだ。chromeのwebrtcライブラリはマルチスレッド動作で、切断イベントが別スレッド側に通知されように作ったが、イベントのタイミングにより切断状態の更新に漏れが生じている可能性がある。

f:id:llamerad-jp:20171005025117p:plain

リソース上限を変更したのだけれども

複数ノードでPROCESSWARPの安定した動作を実現するために、分散メモリの足回りを抜き出して開発中。 100ノード前後でファイルディスクリプタの上限に達したため、以下のページに従い上限を増やす。

christina04.hatenablog.com

なぜかプロセス数の上限が以下のように1064までしか増やせなかった。 まずは1000ノード程度での安定動作を目指そう。

$ uname -a
core file size          (blocks, -c) 0
data seg size           (kbytes, -d) unlimited
file size               (blocks, -f) unlimited
max locked memory       (kbytes, -l) unlimited
max memory size         (kbytes, -m) unlimited
open files                      (-n) 524288
pipe size            (512 bytes, -p) 1
stack size              (kbytes, -s) 8192
cpu time               (seconds, -t) unlimited
max user processes              (-u) 1064
virtual memory          (kbytes, -v) unlimited

追記:max user processesに4096を設定したのがまずかったらしい。hard limit以上は設定できないそうで2048だと設定できた。